How to sum large numbers?

Question

I am trying to calculate 1 + 1 * 2 + 1 * 2 * 3 + 1 * 2 * 3 * 4 + ... + 1 * 2 * ... * n where n is the user input. It works for values of n up to 12. I want to calculate the sum for n = 13, n = 14 and n = 15. How do I do that in C89? As I know, I can use unsigned long long int only in C99 or C11.

1. Input 13, result 2455009817, expected 6749977113
2. Input 14, result 3733955097, expected 93928268313
3. Input 15, result 1443297817, expected 1401602636313

My code:

#include <stdio.h>
#include <stdlib.h>
int main()
{
    unsigned long int n;
    unsigned long int P = 1;
    int i;
    unsigned long int sum = 0;
    scanf("%lu", &n);
    for(i = 1; i <= n; i++)
    {
        P *= i;
        sum += P;
    }
    printf("%lu", sum);
    return 0;
}

Widdershins

You may want to use an external library, like GMP (gmplib.org) – Butylene

What is the limit on n? – Iconic

I don't understand the downvote. The requirements are clear, and a good compilable example is supplied. – Unmixed

@Bathsheba: No research effort is a valid DV reason. "unsigned long range" is not that far-fetched as search term on google or Wikipedia! – Towandatoward

Similar question: #620264 – Jeggar

For that particular case, where you're summing factorials, maybe you can use an almost-closed-form expression like mathworld.wolfram.com/FactorialSums.html (or google for similar results) – Knowitall

@VidorVistrom The limit for n in 15 – Hexapody

Okay..I am formulating a technique for greater ns. Give me some time. – Iconic

@Widdershins Check the answer below – Iconic

in python, lisp there are BigNumbers, they directly implement this. – Citriculture

Your program gives the expected results on 64-bit systems. That is, unless you are using Windows. – Risorgimento

Once I implemented a program for factorial upto 100. The same logic can be used to solve this problem. Here is the code. – Pediculosis

math.stackexchange.com/a/242413/27741 – Intersection

@Pediculosis 0! = 1(sorry, couldn't resist) – Abbreviated

@ringzero; That's a typo. Replace printf("%d\n", num); with printf("%d\n", 1);. – Pediculosis

you cannot put an answer on top by accepting it, answers can be sorted by active/oldest/votes.I can't find an answer by Vidor. – Sepsis

Answer 1

In practice, you want some arbitrary precision arithmetic (a.k.a. bigint or bignum) library. My recommendation is GMPlib but there are other ones.

Don't try to code your own bignum library. Efficient & clever algorithms exist, but they are unintuitive and difficult to grasp (you can find entire books devoted to that question). In addition, existing libraries like GMPlib are taking advantage of specific machine instructions (e.g. ADC -add with carry) that a standard C compiler won't emit (from pure C code).

If this is a homework and you are not allowed to use external code, consider for example representing a number in base or radix 1000000000 (one billion) and code yourself the operations in a very naive way, similar to what you have learned as a kid. But be aware that more efficient algorithms exist (and that real bignum libraries are using them).

A number could be represented in base 1000000000 by having an array of unsigned, each being a "digit" of base 1000000000. So you need to manage arrays (probably heap allocated, using malloc) and their length.

Autostability

Some good advice here. I don't understand the downvote, Time to reverse it! – Unmixed

I think algos for BigNumbers are in Knuth's book. Do you know a better reference for implementing a library of BN such as that one from python or scheme ? – Citriculture

I did read a Springer textbook on BigNums a few years ago. It did mention Knuth (but was not authored by him). Forgot the details – Autostability

But to implement a bignum library inside some language implementation, I would recommend glueing GMPlib – Autostability

@Citriculture GMPlib actually also has a pretty nice documentation of its algorithms (also in the corresponding chapter of the pdf documentation). I don't know if implementing a BN library in an interpreted language is a good idea though. As Basile suggested, I would also try to use GMPlib (many languages have C-bindings, I guess). – Presumably

@chtz: GMPlib is rumored to not be able to handle nicely out-of-memory conditions (it is aborting on that case). For some interpreters it could be wrong. – Autostability

@chtz: "I don't know if implementing a BN library in an interpreted language is a good idea though." – This is totally off-topic here, but well, once in a while, we can have some off-topic fun. Modern high-performance dynamic optimizers are extremely non-intuitive. For example, there's a Ruby gem for manipulating PSDs (Photoshop files). It is implemented as a highly-optimized C extension (for Ruby implementations that support them) and a "fallback" implementation in pure, idiomatic Ruby (for implementations that don't support C extensions such as e.g. Topaz which is an AOT-compiler to … – Faceless

… ECMAScript). And this pure-Ruby fallback implementation does pretty much everything you could conceivably imagine to resist being optimized. E.g. dynamically calling methods from method names stored in runtime strings and such stuff. Looping over an array of method names and reflective calling them. So, you might think that this cannot possibly be fast. But, here's the kicker: Precisely because it is written in Ruby, the TruffleRuby optimizing interpreter can, through multiple rounds of inlining, specialization, and optimization compile the entire test program down to a constant! It is … – Faceless

… significantly faster than using the C extension, since crossing the Ruby-C-barrier is costly. Whereas TruffleRuby happily inlines back and forth between the test program (written in Ruby), the PSD library (written in Ruby) and the Ruby core datastructures (written in Ruby), YARV has nothing to work with: YARV only knows how to run Ruby fast, but the Ruby portion of the code is trivial. YARV has no insight into the Ruby core datastructures (written in C) or the PSD library (written in C). GCC cannot optimize the Ruby code because it doesn't know about it. And every call from Ruby into the … – Faceless

… PSD library is a costly crossing of the VM boundary. In the end, eliminating those cross-language calls buys you back everything and more than you lost from writing the compute-intensive code in Ruby. So, I don't believe that "implementing a BN library in an interpreted language" is that outrageous. The ability to inline the compute-intensive code into the larger application is not to be underestimated. – Faceless

(Off-topic rant over.) :-D – Faceless

The book "BigNum Math" by Tom St. Denis has a nice discussion of the algorithms, together with C implementations. – Erymanthus

Don't try to code your own bignum library. I don't agree with this statement, same as I don't agree wit Don't lay out your own crypto.. Please, try, but don't expect it to be safe, performant and production ready on first attempt. If no one tries, then we won't have any progress. And writing such code is IMHO best way to learn them. – Guerra

Answer 2

You could use a double, especially if your platform uses IEEE754.

Such a double gives you 53 bits of precision, which means integers are exact up to the 53rd power of 2. That's good enough for this case.

If your platform doesn't use IEEE754 then consult the documentation on the floating point scheme adopted. It might be adequate.

Unmixed

Note that unlike a BigInt solution, this will lose precision beyond a certain point. – Zygophyllaceous

Indeed. After the 53rd power of 2 for IEEE754. But so will the built in integral types. So you need to pick the correct type for your job. – Unmixed

Answer 3

A simple approach when you're just over the limit of MaxInt, is to do the computations modulo 10^n for a suitable n and you do the same computation as floating point computation but where you divide everything by 10^r.The former result will give you the first n digits while the latter result will give you the last digits of the answer with the first r digits removed. Then the last few digits here will be inaccurate due to roundoff errors, so you should choose r a bit smaller than n. In this case taking n = 9 and r = 5 will work well.

Kalahari