Exclude loop from progressive cost algorithm

Question

I have an algorithm to calculate the amount of products on target cost. The cost of one product is not constant, it is more expensive by 10%. The target cost may be exceeded if it is closer than the incomplete cost.

I need to optimize code and exclude loop, because it is not effective at high target cost.

This is my working solution with unit test (nunit framework)

public static int CalculateProductAmountOnCost( double targetCost, double productRate )
{
    if ( targetCost <= 0 || productRate <= 0 )
        return 1;

    var previousCollectedCost = 0.0;
    var collectedCost = 0.0;
    var amount = 0;

    for ( ; collectedCost < targetCost; amount++ )
    {
        previousCollectedCost = collectedCost;
        collectedCost += productRate*Math.Pow( 1.1, amount );
    }

    if ( targetCost - previousCollectedCost < collectedCost - targetCost )
        amount -= 1;
    return Math.Max( 1, amount );
}

[Test]
[TestCase( 9, 2, 4 )]
[TestCase( 7, 2, 3 )]
[TestCase( 0, 2, 1 )]
[TestCase( 9, 0, 1 )]
[TestCase( 4.5, 0.2, 12 )]
public void TradeDealHelper_CalculateProductAmountOnGemCostTest( double targetCost, double productRate,
        int expectedAmount )
{
    var actualAmount = TradeDealHelper.CalculateProductAmountOnCost( targetCost, productRate );

    Assert.AreEqual( expectedAmount, actualAmount );
}

So, you're asking for someone to tell you how your code performance? — juanferrer, Jul 13 '17 at 09:56
@JuanFerrer I'm asking for help in writing this algorithm without a loop, I tried a few options, but they do not pass the tests — Dmitry, Jul 13 '17 at 09:58
I was working on an answer, but I only managed to shave off about 0.07 seconds after testing with 500k calls. Can't think of a better way of doing it, sorry. — juanferrer, Jul 13 '17 at 11:05

Dan Dumitru · Accepted Answer · 2017-07-13T11:34:29.930

public static int CalculateProductAmountOnCost2(double targetCost, double productRate)
{
    if (targetCost <= 0 || productRate <= 0)
        return 1;

    var amount = (int)Math.Floor(Math.Log(((targetCost / (productRate * 10)) + 1), 1.1) - 1);

    var lowerCost = productRate * 10 * (Math.Pow(1.1, amount + 1) - 1);
    var upperCost = productRate * 10 * (Math.Pow(1.1, amount + 2) - 1);

    if (targetCost - lowerCost > upperCost - targetCost)
        amount++;

    return Math.Max(1, amount + 1);
}

There is a bit of math you can use. What follows is basically mathematical stuff, not code.

Your total cost is:

totalCost = productRate + productRate * 1.1 + productRate * (1.1 ^ 2) + ... + productRate * (1.1 ^ n)

Which can be rewritten as:

totalCost = productRate * (1 + 1.1 + 1.1 ^ 2 + ... 1.1 ^ n)

There is a formula to calculate that sum:

1 + a + a ^ 2 + ... a ^ n = (a ^ (n + 1) - 1) / (a - 1)

So your total cost is now:

totalCost = productRate * ((1.1 ^ (n + 1) - 1) / (1.1 - 1))

totalCost = productRate * 10 * (1.1 ^ (n + 1) - 1)

We apply this last formula to find n for your targetCost, and we get:

n = Math.Log((targetCost / (productRate * 10)) + 1, 1.1) - 1

(that's logarithm in base 1.1)

The code is applying these formulas.

Exclude loop from progressive cost algorithm

1 Answers1