How to compute 10000! without mult/div/mod

Question

This is intended as a programming challenge. Faster solutions better. Note cannot use normal primitives.

Answer 1

The only way I can think of doing this with without mult, div or mod is to do bit shifts. Basically you would be trying to find the number of bit shifts to make, make them, and then add any remaining values.

Answer 2

You can implement multiplication using successive addition (or "Russian Peasant Multiplication"), then multiply all the integers from 2 through 10000. It won't be very efficient.

Answer 3

Well, in general algorithm terms:

m * n

can be expressed as

total = 0
for i = 1 to n
  total += m
end

so it simply becomes

total = 1
for i = 1 to 10000
  new total = 0
  for j = 1 to i
    new total += total
  end for
  total = new total
end for

and you'll need arbitrary precision arithmetic to do it but that's fairly trivial, particularly for addition of integers.

Edit: added working PHP implementation without the arbitrary precision arithmetic:

for ($i=1; $i<10; $i++) {
  echo $i . ' = ' . fact($i) . "\n";
}

function fact($n) {
  $total = 1;
  for ($i=1; $i<=$n; $i++) {
    $new_total = 0;
    for ($j=1; $j<=$i; $j++) {
      $new_total += $total;
    }
    $total = $new_total;
  }
  return $total;
}

Output:

1 = 1
2 = 2
3 = 6
4 = 24
5 = 120
6 = 720
7 = 5040
8 = 40320
9 = 362880

Answer 4

You can precompute the answer, store it in a constant tring, and then copy the string to the screen. Should be the fastest way to accomplish the goal.

Answer 5

This is quick enough for me, at least, in Haskell, running on a 1.6GHz Atom N270, background processes around 50% load:

$ time ghci -e "product [2..10000]" > /dev/null

real    0m2.227s
user    0m1.984s
sys 0m0.056s

$ ghci -e "product [2..10000]" | head -c 1024
2846259680917054518906413212119868890148051401702799230794179994274411340003764443772990786757784775815884062142317528830042339940153518739052421161382716174819824199827592418289259787898124253120594659962598670656016157203603239792632873671705574197596209947972034615369811989709261127750048419884541047554464244213657330307670362882580354896746111709736957860367019107151273058728104115864056128116538532596842582599558468814643042558983664931705925171720427659740744613340005419405246230343686915405940406622782824837151203832217864462718382292389963899282722187970245938769380309462733229257055545969002787528224254434802112755901916942542902891690721909708369053987374745248337289952180236328274121704026808676921045155584056717255537201585213282903427998981844931361064038148930449962159999935967089298019033699848440466541923625842494716317896119204123310826865107135451684554093603300960721034694437798234943078062606942230268188522759205702923084312618849760656074258627944882715595683153344053442544664841689458042

And at least it's fast in the sense that it took me about as long to run as it did to write :)

Answer 6

total = 1
for i = 1 to 10000
  new total = 0
  for j = 1 to i
    new total += total
  end for
  total = new total
end for

The above code will take forever.

I would want to write my own multiplication function.

Do we have numbers stored as strings, or bignums, or what?

Can't use Russian prasant multiplication because for that you need div.

Answer 7

Edit: In case someone comes in with a "tuned" version of this, I must state I came up with this on my own & before anything similar was posted. ;)

Via careful application of the binomial theorem and binary multiplication, I've got this running in 4 seconds. It saves some 9800 out of 9999 "slow multiplications" required by the naive algorithm. I left a couple instances of x/2 and x%2 because they are effectively shift and mask.

[TestMethod]
public void FactorialTest()
{
    List<BigInteger> numbers = new List<BigInteger>(Enumerable.Range(1, 10000).Select(i => (BigInteger)i));
    BigInteger expected = numbers.Aggregate((BigInteger)1, BigInteger.Multiply);

    Stopwatch watch = Stopwatch.StartNew();
    // right now I was just caching it to see the progress
    List<BigInteger[]> cache2 = new List<BigInteger[]>();
    BigInteger[] numbers2 = Enumerable.Range(1, 10000).Select(i => (BigInteger)i).ToArray();
    cache2.Add(numbers2);
    int stage = 0;
    List<BigInteger> extra = new List<BigInteger>();
    // "fast fold" while it will still save multiplications
    while (numbers2.Length > (2 << stage))
    {
        if (numbers2.Length > 1 && (numbers2.Length % 2) == 1)
        {
            extra.Add(numbers2[numbers2.Length / 2]);
            var numberList = numbers2.ToList();
            numberList.RemoveAt(numberList.Count / 2);
            numbers2 = numberList.ToArray();
        }

        numbers2 = FastFold(numbers2, stage);
        cache2.Add(numbers2);
        stage++;
    }

    BigInteger[] lastCache = cache2[cache2.Count - 1];
    BigInteger result = lastCache[0];
    for (int i = 1; i < lastCache.Length; i++)
        result = SlowMultiply(result, lastCache[i]);
    for (int i = 0; i < extra.Count; i++)
        result = SlowMultiply(result, extra[i]);

    TimeSpan elapsed = watch.Elapsed;
    Trace.WriteLine(elapsed);

    Assert.AreEqual(expected, result);
}

// THIS CORRUPTS THE INPUT ARRAY
public BigInteger[] MultiDeriv(BigInteger[] numbers)
{
    BigInteger[] result = new BigInteger[numbers.Length - 1];
    for (int i = 0; i < result.Length; i++)
    {
        for (int j = 0; j < numbers.Length - i - 1; j++)
        {
            numbers[j] = numbers[j + 1] - numbers[j];
        }

        result[i] = numbers[0];
    }

    return result;
}

public BigInteger[] FastFold(BigInteger[] numbers, int stage)
{
    // shift, mask, add
    BigInteger[] result = new BigInteger[numbers.Length / 2 + numbers.Length % 2];

    for (int i = 0; i <= (2 << stage) && i < result.Length; i++)
    {
        result[i] = SlowMultiply(numbers[i], numbers[numbers.Length - i - 1]);
    }

    BigInteger[] integrationArray = MultiDeriv(result.Take((2 << stage) + 1).ToArray());

    for (int i = 0; i < (2 << stage) - 1; i++)
        Integrate(integrationArray);

    for (int i = (2 << stage) + 1; i < result.Length; i++)
    {
        Integrate(integrationArray);
        result[i] = result[i - 1] + integrationArray[0];
    }

    return result;
}

public void Integrate(BigInteger[] integrator)
{
    for (int i = 0; i < integrator.Length - 1; i++)
    {
        integrator[i] += integrator[i + 1];
    }
}

public BigInteger SlowMultiply(BigInteger x, BigInteger y)
{
    if (x > y)
        return SlowMultiply(y, x);

    if (x.IsZero)
        return 0;

    if (x.IsOne)
        return y;

    BigInteger result = 0;
    while (!x.IsZero)
    {
        if (!x.IsEven)
            result += y;

        x >>= 1;
        y <<= 1;
    }

    return result;
}