How can I improve this algorithm?

Question

What I am trying to accomplish is to take a US Currency amount, and break it down into how many of each bill and coin it takes to make that amount using the least of each type.

I wrote this in a hurry, and it works, but I feel like it could be improved. Also, I had to round the remainder because I was getting a strange result once it got to something like (0.13 - (1 * 0.1) instead of 0.3 it would come out to 0.299999995

The code below does seem to work.

function moneybreak ($amount, $sizebill) {
    // get units of sizecurrency
    $numbills = floor($amount / $sizebill);
    $remainder = $amount - ($numbills * $sizebill);
    $remainder = round($remainder, 2);
    $ret['bills'] = $numbills;
    $ret['remain'] = $remainder;
    return $ret;
}

$amount = 1999.99;
$money = array();
$tmoney = moneybreak($amount, 500);
$money['fivehundred']   = ($tmoney['bills'] > 0) ? $tmoney['bills'] : 0.00;
$tmoney = moneybreak($tmoney['remain'], 100);
$money['onehundred']        = ($tmoney['bills'] > 0) ? $tmoney['bills'] : 0.00;
$tmoney = moneybreak($tmoney['remain'], 20);
$money['twenty']            = ($tmoney['bills'] > 0) ? $tmoney['bills'] : 0.00;
$tmoney = moneybreak($tmoney['remain'], 10);
$money['ten']               = ($tmoney['bills'] > 0) ? $tmoney['bills'] : 0.00;
$tmoney = moneybreak($tmoney['remain'], 5);
$money['five']              = ($tmoney['bills'] > 0) ? $tmoney['bills'] : 0.00;
$tmoney = moneybreak($tmoney['remain'], 1);
$money['one']               = ($tmoney['bills'] > 0) ? $tmoney['bills'] : 0.00;
$tmoney = moneybreak($tmoney['remain'], 0.25);
$money['quarter']           = ($tmoney['bills'] > 0) ? $tmoney['bills'] : 0.00;
$tmoney = moneybreak($tmoney['remain'], 0.1);
$money['dime']              = ($tmoney['bills'] > 0) ? $tmoney['bills'] : 0.00;
$tmoney = moneybreak($tmoney['remain'], 0.05);
$money['nickle']            = ($tmoney['bills'] > 0) ? $tmoney['bills'] : 0.00;
$tmoney = moneybreak($tmoney['remain'], 0.01);
$money['penny']         = ($tmoney['bills'] > 0) ? $tmoney['bills'] : 0.00;

This is why we don't use floating-point values for currency. — Ignacio Vazquez-Abrams, Jan 30 '11 at 00:23
I'd store cents as integer. As For the breaking into bits you could use modulo `%`. — Flying Swissman, Jan 30 '11 at 00:33
You might be interested in the [code review](http://codereview.stackexchange.com/) site, which recently went into public beta. — moinudin, Jan 30 '11 at 00:38

score 5 · Accepted Answer · edited May 23 '17 at 09:58

Your question is a perfect example of why you shouldn't use floating-point arithmetic to represent currency.

First, you'll need to avoid floating-point numbers like you owe them a lot of money (though actually it might be the opposite). To that end, we'll do our calculations with cents instead of dollars. Any amount you might have needs to be multiplied by 100.

You can then rather easily get away by listing all the money units you want to use ($100, $50, $20, ...) into an array, and sort it in descending order so the biggest ones come out first.

<?php

// money units, in cents
// (reflecting common Canadian currency)
$units = array(10000, 5000, 2000, 1000, 500, 200, 100, 25, 10, 5, 1);
function moneyBreak($amount, $units)
{
    // ensure the array is sorted in descending order
    rsort($units);
    $itemsOfEach = array();
    // loop through all the money units
    foreach ($units as $unit)
    {
        // you'll try to use this money unit for the largest possible
        // amount of money
        $itemsOfEach[$unit] = intval($amount / $unit);
        // and once you're done, you'll continue with the remainder
        $amount %= $unit;
    }
    return $itemsOfEach;
}

?>

And here is an example:

$amount = 32347; // $323.47
$result = moneyBreak($amount, $units);
print_r($result);
/* prints this:
Array
(
    [10000] => 3
    [5000] => 0
    [2000] => 1
    [1000] => 0
    [500] => 0
    [200] => 1
    [100] => 1
    [25] => 1
    [10] => 2
    [5] => 0
    [1] => 2
)
*/

Thanks for the level of detail provided. I now realize why using integer values for the currency is a much safer solution. — merlincam, Jan 30 '11 at 00:35

score 2 · Answer 2 · answered Jan 30 '11 at 00:34

A quick way to do what you want if I understood the question correctly.

$amount = 1999;
$values = array(500, 100, 20, 10, 5, 1);
$result = array();

foreach($values as $value) {
    $result[$value] = floor($amount / $value);
    $amount = $amount % $value;
}

Just work in the smaller sums too as you see fit.

Edit: Actually, come to think of it the floor part will ofc break when it goes below 1 so you need to add a check for when $amount < 1

score 2 · Answer 3 · answered Jan 30 '11 at 00:34

Well, since you're doing the same thing over and over again, you could do something like this:

$denominations = array(
                      'fivehundred'=>500,
                      'onehundred'=>100,
                      'twenty'=>20,
                      'etc'=>'etc' //The rest of the denominations
                      );

$amount = 1999.99;
$money = array();

foreach($denominations as $word => $num)
{
     $tmoney = moneybreak($amount, $num);
     $money[$word] = ($tmoney['bills'] > 0) ? $tmoney['bills'] : 0.00;
}

Though, zneak's answer is nice. If combined with the array which includes the keys for the denominations in mine, and modifying his foreach($units as $units) to foreach($units as $key => $unit), you could get an array that has the proper key for each unit ("onehundred","fives", etc.).

How can I improve this algorithm?

3 Answers3