# Transactions on lists of coins of different values

For learning purposes, I am developing the first steps of an idle game with exponentially higher income numbers. Usual int, long, etc. can't store big enough numbers for that.

I looked through many threads which I found on google and using a list (or an array) which is separated in e.g. bronze coins, silver coins, gold coins, etc. seems to be the cleanest version.

In my first approaches I created this list:

namespace Coins
{
public class script_coinHandler : MonoBehaviour
{
public List<Coin> coinList = new List<Coin>() // list based on the "Coin" class
{
new Coin() { Name = "bronze"},
new Coin() { Name = "silver"},
new Coin() { Name = "gold"},
new Coin() { Name = "diamond"},
};
}

public class Coin
{
public string Name { get; set; }
public int Amount { get; set; }
public int Multiplier { get; set; }
}

}


I want each coin type to go up to 999999. This means 1 silver = 1000000 bronze, 1 gold = 1000000 silver.

I can't get my head around a way to do maths with this list. Example:

Player has 3000 GOLD, 320000 SILVER, 524321 BRONZE

Player wants to buy something for 20 GOLD, 120000 SILVER, 300000 BRONZE

Just subtracting 20 from GOLD, 120000 from SILVER, and 300000 from BRONZE won't always work. For example when a Player has no BRONZE but some SILVER - you can't subtract 300000 BRONZE without converting SILVER to BRONZE first.

Q: What would be an efficient function to subtract the price from the total amount? What about multiplying and dividing? Accuracy is not important. When spending a few GOLD, nobody will care about 10000 BRONZE.

• Why do you still have in that case the Bronze part? Usually those idle games go in a really steep price and you only ever see the highest value as a cost / the one right below it. Your example would be on a display like 20.12 Goldcoins - not 20.1200003 Goldcoins Feb 24, 2021 at 12:38
• You're right, it would be sufficient to only show and calculate 2 coin types. I do not want to use just one coin type with decimals though, as "full coins" are easier to grasp for the user.
– LWun
Feb 24, 2021 at 12:43
• Welcome to GDSE. If you're looking for a system that works with any &all arbitrary multipliers, the problem gets very messy. If you're willing to restrict the denominations, then the greedy algorithm work. Are you willing to accept answers that will only guarantee results for 'nice' currency multipliers? Feb 24, 2021 at 14:51
• I’m currently working on an idle game and the framework we are using uses doubles to store all currency values. It is inexact at very high values, but does it matter if you lose single-coin precision when you already have 1E24 coins, and you’re earning 1E20 every second? Any spending of currency that would get lost in the precision would be earned back immediately anyway. Feb 25, 2021 at 14:04

I would internally represent all money values in the game in bronze coins, and then do the conversion to the diamond/gold/silver/bronze representation only when presenting values on the UI. That makes a lot of things a lot easier for you, notably doing arithmetic with money.

Unfortunately the number range you need goes up to 10^24, which does not fit into a long (64 bit integer). But you can solve that problem by using the type BigInteger. It can handle integer values of practically unlimited size. It supports all the C# standard math operators like + or *.

When you want to initialize a BigInteger with a value which is too large to be represented by a long, then create a string representation of that value and use BigInteger.Parse(bronzeValueAsString).

Edit: A comment asked for performance. So I wrote a script which takes a 44 digit number and calculates the hailstone sequence from it, a simple but neat number crunching algorithm combining multiplication, division, addition and odd/even checks. And I even used a BigInteger for the loop counter, which would not even have been necessary in this case.

using UnityEngine;
using System.Numerics;

public class BigIntegerHailstone : MonoBehaviour
{
void Update()
{
BigInteger current = BigInteger.Parse("9999999999999999999999999999999999999999999");
BigInteger count = BigInteger.Zero;
while (current != BigInteger.One) {
count++;
if (current.IsEven) {
current /= 2;
} else {
current = current * 3 + 1;
}
}
Debug.Log(count);
}
}


The number of loop-iterations for that number is 1402. A scene with this script on an object ran with ~500 FPS on my machine (Core i5-6600). The profiler says this took under 1.6 millisecond to calculate:

• Can you tell me something about the performance of BigInteger? I want this application to run on mobile. What about going into ranges of 1*10^44 (which may be the limit) and adding coins a few times per second? Would the math have a big impact on performance?
– LWun
Feb 24, 2021 at 15:38
• @LWun When you are not sure, you could do a couple benchmarks of your own. But my intuition says that the performance impact should not become measurable until you perform thousands of operations per frame. And I would be surprised if any implementation for big integer math you could program yourself would be notably faster than the standard library. Feb 24, 2021 at 16:04
• @LWun I did a little performance test and added it to the answer. Feb 24, 2021 at 17:02

Here's how we could do this with lists of integers representing the number of coins of each denomination held, added, or required for the price, in ascending order of value. These are effectively digits in a base-one-million number. Where we're not holding any coins of a particular denomination, or a price/increment does not include any coins of that denomination, we store a zero. We can omit zeroes for denominations above and beyond the value we're representing.

So the list {1, 0, 3} means "1 Bronze coin, 0 Silver coins, 3 Gold coins, no Diamonds or higher"

I also assume that the inputs/inventory are always expressed in "lowest terms" — so you never have a price of 2 million Bronze coins, instead that would be represented as 2 Silver coins and 0 Bronze coins.

The version below is not thread-safe, so if you want to interact with the player's purse over multiple threads, you'll want to add some locks or more sophisticated transaction handling.

// You could also make this a lookup table with distinct values at each denomination.
const int COIN_STEP_SIZE = 1000000;

// Number of each coin held, in order from least to most valuable coin type.
// Intermediate coins you lack are present as placeholder 0 values.
List<int> _inventory = new List<int>();

Stack<bool> _borrow = new Stack<bool>();

// Deduct the money only if we can afford it, otherwise do nothing.
// Report back whether the transaction was successful.
public bool TryDeduct(List<int> price) {
if (CanAffort(price)) {
DeductWithLoggedBorrows(price);
return true;
}

return false;
}

// Check if we can pay the price, without mutating the inventory.
public bool CanAfford(List<int> price) {
_borrow.Clear();

// Initialize the scratch pad with a guard value.
// "We have not borrowed any Bronze coins from lower denominations" (there are none)
_borrow.Push(false);

// Iterate over the price, from lowest to greatest value coin denominations.
for (int denomination = 0; denomination < _inventory.Count; denomination++) {
// If we had to borrow from this coin to pay the previous one, add one to the price.
int required = borrow.Peek() ? 1 : 0;

// Coins above the top end of the price are treated as zero price.
if (denomination < price.Count) required += price[denomination];

// If we don't have enough of this coin, log a borrow from the next.
if (_inventory[denomination] < required) {
_borrow.Push(true);
} else {
// Otherwise, if we've handled all the coins in the price,
// we know we can afford this!
if (denomination >= (price.Count - 1)) return true;

// Or, we log "no borrow from next required" and continue.
_borrow.Push(false);
}
}

// We still had more to borrow when we hit the end of the player's inventory,
// so we cannot afford this.
return false;
}

// Mutate the inventory, only after we've determined that we can afford it,
// and logged where we need to do borrowing.
private void DeductWithLoggedBorrows(List<int> price) {
// Start at the top denomination we had to check to pay the price,
// and work our way back down to the lowest denomination.
for (int denomination = _borrow.Count - 1; denomination >= 0; denomination--) {
bool borrow = _borrow.Pop();

int required = borrow ? 1 : 0;
if (denomination < price.Count) required += price[denomination];

inventory[denomination] -= required;

// If we borrowed here, add the change to the denomination below.
// (This will never go out of bounds because we initialize the stack with false)
if (borrow) inventory[denomination - 1] += COIN_STEP_SIZE;
}
}

int carry = 0;
int denomination;
for (denomination = 0; denomination < coins.Count; denomination++) {
_inventory[denomination] += coins[denomination] + carry;

if (_inventory[denomination] >= COIN_STEP_SIZE) {
carry = _inventory[denomination] / COIN_STEP_SIZE;
_inventory[denomination] -= carry * COIN_STEP_SIZE;
} else {
carry = 0;
}
}

while (carry > 0) {
_inventory[denomination] += carry;

if (_inventory[denomination] >= COIN_STEP_SIZE) {
carry = _inventory[denomination] / COIN_STEP_SIZE;
_inventory[denomination] -= carry * COIN_STEP_SIZE;
} else {
carry = 0;
}
}
}