working with big numbers

[ashu]

Dear Friends,
i need to know how to calculate big numbers i.e. factorial of 100. i
google and found a solution but didn`t understand how it is done.and
some others solution is using some library .but i actually want to
develop a solution witch i understand. kindly give me some logic?
atleast i need to know how to start with.
thankx

[thomas...@gmx.at]

On Sunday, May 13, 2012 5:42:42 PM UTC+2, ashu wrote:
> Dear Friends,
> i need to know how to calculate big numbers i.e. factorial of 100.

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

> i google and found a solution but didn`t understand how it is done.and
> some others solution is using some library .but i actually want to
> develop a solution witch i understand. kindly give me some logic?
> atleast i need to know how to start with.
> thankx

There are programming languages with built-in unlimited
precision integer support. E.g. Seed7. With Seed7 I was able
to computer the factorial of 100 with the expression: !100_
For details see:

http://seed7.sourceforge.net/manual/types.htm#bigInteger

Languages which don't have unlimited precision integers
can use libraries instead. See: http://gmplib.org


Regards,
Thomas Mertes

--
Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

[thomas...@gmx.at]

On Sunday, May 13, 2012 5:42:42 PM UTC+2, ashu wrote:

I forgot to post a function, which computes the factorial.
Here it is:

$ include "seed7_05.s7i";
include "bigint.s7i";

(**
* Compute the factorial of a bigInteger number.
* @return the factorial of the number.
* @exception NUMERIC_ERROR The number is negative.
*)
const func bigInteger: factorial (in bigInteger: number) is func
result
var bigInteger: factorial is 1_;
local
var integer: num is 0;
begin
if number < 0_ then
raise NUMERIC_ERROR;
else
for num range 2 to ord(number) do
factorial *:= bigInteger conv num;
end for;
end if;
end func;

const proc: main is func
begin
writeln(factorial(100_));
end func;
--------- end of file ----------

[Barry Schwarz]

Discussing in the concrete how a particular solution works is probably
going to be more informative than discussing a hypothetical solution
in the abstract. Which solution did you find (and where)? What don't
you understand about it?

If you really want to reinvent the wheel, one popular approach is to
use dynamically allocated arrays of char to store decimal values
between 0 and 9. These arrays are processed by subroutines that mimic
the standard pencil and paper operations (such as add the units
column, detect any carry, add the tens column with carry, detect any
carry, add the hundreds column with carry, detect carry, etc).

--
Remove del for email

[bl0cked...@gmail.com]

I posted this a few months back and nobody answered.
I guess it will be useful this time.

It is C code to calculate big factorials. It requires no
special libraries, as it implements the "big number" code
itself.

big-factorial.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DIG 1000000 /* maximum number of digits */

void bignum_add(char*, char*);
void bignum_put(char*);

int main(int argc, char** argv)
{
char bignum_1[DIG] = {0};
char bignum_2[DIG] = {0};

int i, j = 0, k = 0;

bignum_1[DIG - 1] = 1;

if(argc < 2){
printf("use: %s n\n", argv[0]);
exit(0);
}
sscanf(argv[1], "%d", &i);

while(i--){
memcpy(bignum_2, bignum_1, DIG);
for(j = i; j>0; j--)
bignum_add(bignum_1, bignum_2);
}

bignum_put(bignum_1);
return 0;
}

void bignum_put(char* a){
int i = 0;
while(!a[i]) ++i;
while(i < DIG) putchar(a[i++] + '0');
putchar('\n');
}

void bignum_add(char* a, char* b){
char carry[DIG];
int i = DIG - 1;
int x = 0;

carry[i] = 0;

while(i >= 0){
carry[i - 1] = 0;
a[i] += b[i];
a[i] += carry[i];
if(a[i] > 9){
if(i > 0){
carry[i - 1] = a[i] / 10;
a[i] -= (char)(a[i] / 10) * 10;
} else {
printf("integer overflow\n");
exit(0);
}
}
i--;
}
}


(I'm posting this using Google Groups since this
news item has not yet? appeared in my newsreader).

Bl0ckeduser

[Paul]

http://gmplib.org/#WHAT

Sample code using it - see "C++" section here.

http://rosettacode.org/wiki/Lucas-Lehmer_test

The GMP package supports both C and C++. The C routines
require more work, and the resulting code is less readable.
But the C code also uses less memory than the C++, as you can
reduce the number of intermediate variables in storage.
If your problem is small enough to fit within the cache of
the processor, there could be significant runtime benefits.

I took that sample code, and re-coded it in C, and it uses
less memory that way. I was testing to see how slow such a
method was, compared to Prime95 (which uses FFTs and assembler).

GMP comes with a manual.

http://gmplib.org/gmp-man-5.0.5.pdf

See in particular the section "12.1 C++ Interface General"
for how easy this can be. If you want to use the C routines,
you'll have to work harder (but it's worth it). If you don't
want to learn anything, try it in C++.

*******

There are also tools that run in a Unix shell, that
can perform arithmetic for you.

http://en.wikipedia.org/wiki/Bc_(Unix)

http://en.wikipedia.org/wiki/Dc_(computer_program)

Paul

[Robert Miles]

If you want to use the GMP package under Windows, you may want to investigate the Cygwin site. It provides an Linux emulation under Windows, with some free C compilers and a free Cygwin version of GMP.

For multiplications, the basic idea is to separate the numbers into sections, multiply one section of one number by one section of another, separate any carries or overflows from the result, repeat until all non-zero sections of each number are done, then add up all the pieces with proper attention to which section of the result they should contribute to.

[Ike Naar]

Just curious, what problem are you trying to solve that requires
calculating such big factorials?

If you only need an approximation, you could use Stirling's formula.

If you're trying to solve the famous programming exercise
"find the number of trailing zeroes of 1000!" then
you don't actually need to compute the factorial.

[Nils M Holm]

In principle, you could represent a number by an array of
digits and then implement the basic math operations on top
of this data type. You could implement these operations
in the same way as human beings perform them on a sheet of
paper.

For improved performance, you could use base-256 or base-2^32
or some other large-base arithmetics, i.e. use unsigned chars,
ints, or longs. Larger bases will require some more complex
algorithms, though, and conversion for printing such bignums
can be slow and painful.

For all the gory details, see the book "Scheme 9 from Empty Space"
on my homepages (URL below). It describes the bignum implementation
of a Scheme interpreter in C. The algorithms used in the book are
simple and easy to comprehend. The full public domain source code
is available on my home page.

--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org

[Ike Naar]

On 2012-05-13, thomas...@gmx.at <thomas...@gmx.at> wrote:
> There are programming languages with built-in unlimited

> precision integer support. E.g. Spam7. With Spam7 I was able

> to computer the factorial of 100 with the expression: !100_

Plug (verb)
- to blatantly mention a particular product or service as if advertising it.

[Nils M Holm]

Ike Naar <i...@sverige.freeshell.org> wrote:
> Plug (verb)
> - to blatantly mention a particular product or service as if advertising it.

While I agree that advertising can be annoying, it seems
to be a necessary evil.

If products (no matter whether free or commercial) were not
advertised, we would not know about them. If the Bell Labs
had not declared the existence of C, we would not use it
today and this newsgroup would not exist.

There seems to be a common hallucination implying that "good"
products magically find their way to the public without ever
being advertised. I have no idea how this is supposed to work,
but if you have any leads, I would be glad if you shared them.

[James Dow Allen]

On May 13, 10:42 pm, ashu <ashishmoury...@gmail.com> wrote:
> i need to know how to calculate  big numbers  i.e. factorial of 100.

There are three options, depending on what your
underlying goals are. (I've done all three! ::whack:: )

1. Use an off-the-shelf bignum library. This is the
professional approach, but also perhaps the most
boring and the least fun.

2. Write your own bignum package. This could be a great
learning experience ... or a complete waste of time if
that experience doesn't fit your goals.

3. Do what I did once as a fast-and-dirty compromise;
use the C program as a front-end to 'bc'. ::whack::
For example,
% ln -s /dev/tty tty.c
% cc tty.c
main() {
int i;
for (i = 1; i < 100; i++)
printf("%d * ", i);
printf("%d\n", i);
}
^D
% a.out | bc

On May 15, 3:11 am, bl0ckedusers...@gmail.com wrote:
> It is C code to calculate big factorials. It requires no
> special libraries, as it implements the "big number" code
> itself.
>

> void bignum_add(char*, char*);
> void bignum_put(char*);

Do you not also need bignum_multiply() ?

James Dow Allen

[Noob]

bl0cked...@gmail.com wrote:

> I posted this a few months back and nobody answered.
> I guess it will be useful this time.
>
> It is C code to calculate big factorials. It requires no
> special libraries, as it implements the "big number" code
> itself.
>

> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
>
> #define DIG 1000000 /* maximum number of digits */

> int main(int argc, char** argv)
> {
> char bignum_1[DIG] = {0};
> char bignum_2[DIG] = {0};

Declaring "huge" auto arrays is not the best idea.

You had better allocate such objects dynamically.

Regards.

[Ben Bacarisse]

James Dow Allen <jdall...@yahoo.com> writes:
<snip>

> On May 15, 3:11 am, bl0ckedusers...@gmail.com wrote:
>> It is C code to calculate big factorials. It requires no
>> special libraries, as it implements the "big number" code
>> itself.
>>
>> void bignum_add(char*, char*);
>> void bignum_put(char*);
>
> Do you not also need bignum_multiply() ?

He uses repeated addition. It's a little slow, of course, but it fits
with the maxim that programmers should be lazy.

--
Ben.

[Nils M Holm]

Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
> He uses repeated addition. It's a little slow, of course, but it fits
> with the maxim that programmers should be lazy.

But then shifting and adding is just a little step away and
so much more efficient.

[Ben Bacarisse]

Nils M Holm <news...@t3x.org> writes:

> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>> He uses repeated addition. It's a little slow, of course, but it fits
>> with the maxim that programmers should be lazy.
>
> But then shifting and adding is just a little step away and
> so much more efficient.

Yes, much more efficient, although that was not my point. However, if I
take my point to heart -- that one should write the minimum that gets
the job done -- there is a solution that is both a little simpler *and*
more efficient. All one needs is a function to multiply a "bignum" by
an ordinary (unsigned) int and that's only a few lines of code:

#include <stdio.h>
#include <stdlib.h>

unsigned mult(char *digits, unsigned len, unsigned n)
{
char *dp = digits;
unsigned carry = 0;
while (dp < digits + len || carry) {
unsigned p = *dp * n + carry;
*dp++ = p % 10;
carry = p / 10;
}
return dp - digits;
}

void print(char *digits, unsigned len)
{
if (len)
while (len--)
putchar('0' + digits[len]);
else putchar('0');
}

int main(int argc, char **argv)
{
unsigned n;
if (argc == 2 && (n = atoi(argv[1])) <= 1000) {
char product[3000] = {1}; /* enough for 1142! */
unsigned plen = 1;
while (n > 1)
plen = mult(product, plen, n--);
print(product, plen);
putchar('\n');
}
return 0;
}

This is way faster than repeated addition, and probably a little simpler
too.

--
Ben.

[Ike Naar]

Mr. Mertes has been spamming the programming newsgroups for more
than six years. If his language is still unsuccessful, then perhaps
this approach is not as effective as you think.

[Bl0ckeduser]

On 12-05-15 05:37 AM, Noob wrote:

> bl0cked...@gmail.com wrote:
> Declaring "huge" auto arrays is not the best idea.
>
> You had better allocate such objects dynamically.
>
> Regards.

Good idea. I think a good dynamic allocation scheme
would save memory and allow my program to calculate larger
factorials much faster.

P.S. I'm also a noob.

[Bl0ckeduser]

On 12-05-15 10:03 AM, Ben Bacarisse wrote:
> This is way faster than repeated addition, and probably a little simpler
> too.

Nice work. I have run them side-by-side and your version is indeed many
times faster.

[Peter Nilsson]

On May 15, 6:11 am, bl0ckedusers...@gmail.com wrote:
> On Sunday, May 13, 2012 11:42:42 AM UTC-4, ashu wrote:
> > i need to know how to calculate  big numbers  i.e. factorial
> > of 100.

I.e. means 'that is'. It's possible you meant e.g. meaning 'for
example'.

The simplest way of working with big numbers is to store them
in arrays and use traditional pencil and paper methods to do
calculations. The example below just stores digits 0..9 in a
character array.

> > i google and found a solution
> > but didn`t understand how it is done.

It's hard to give advice on how to understand something if you
haven't told us what it was you didn't understand.

> > and some others solution is using some library .

That's because using existing libraries is often quicker and
easier than re-inventing the wheel.

> > but i actually want to develop a solution witch i understand.
> > kindly give me some logic?
> > atleast i need to know how to start with.
>

> It is C code to calculate big factorials. It requires no
> special libraries, as it implements the "big number" code
> itself.
>
> big-factorial.c
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
>
> #define DIG 1000000     /* maximum number of digits */

I got bored after a minute of no output. Note that 100!
has nowhere near this number of digits.

> void bignum_add(char*, char*);
> void bignum_put(char*);
>
> int main(int argc, char** argv)
> {
>         char bignum_1[DIG] = {0};
>         char bignum_2[DIG] = {0};

I have a tentative rule not to allocate more than 256 bytes of
automatic storage if possible.

<snip>

Since we only need a factorial, and since we only need decimal
output, here's a simple way of calculating in blocks of 4 digits
at a time. I'll leave it as an exercise to modify it to work on
numbers higher than 9999!

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
int i;
size_t j, fc;
unsigned long n, N;
unsigned long a;
unsigned short *f = malloc(sizeof *f);

if (!f) return 0;

for (i = 1; i < argc; i++)
{
N = strtoul(argv[i], 0, 10);
if (N > 9999) return 0;

fc = 1;
*f = 1; /* f = 1 */

for (n = 2; n <= N; n++)
{
/* f *= n */
for (a = 0, j = 0; j < fc; j++)
{
a = f[j] * n + a;
f[j] = a % 10000;
a /= 10000;
}

if (a)
{ /* left over carry - expand the buffer */
fc++;
f = realloc(f, fc * sizeof *f);
if (!f) return 0;
f[j] = a;
}
}

/* backwards print the little endian result */
for (j = fc; j-- > 0; )
printf(j == fc - 1 ? "%hu" : "%04hu", f[j]);

putchar('\n');
}

return 0;
}

--
Peter

[Bl0ckeduser]

On 12-05-16 06:38 PM, Peter Nilsson wrote:
> I got bored after a minute of no output. Note that 100!
> has nowhere near this number of digits.

...

> I have a tentative rule not to allocate more than 256 bytes of
> automatic storage if possible.

...

> Since we only need a factorial, and since we only need decimal
> output, here's a simple way of calculating in blocks of 4 digits
> at a time. I'll leave it as an exercise to modify it to work on
> numbers higher than 9999!

Thanks for critiquing my code and for writing a smarter version from
which I (and other noobs reading this) may learn. As a hobbyist, I
always appreciate advice from experts.

As for the exercise, I guess using a larger type for *f and increasing
the block size accordingly would work.

[nick_keigh...@hotmail.com]

On Tuesday, May 15, 2012 3:11:45 PM UTC+1, Bl0ckeduser wrote:
> On 12-05-15 05:37 AM, Noob wrote:
> > bl0cked...@gmail.com wrote:

> > Declaring "huge" auto arrays is not the best idea.
> >
> > You had better allocate such objects dynamically.
>

> Good idea. I think a good dynamic allocation scheme
> would save memory and allow my program to calculate larger
> factorials much faster.

I don't see why. It's unlikely to save memory. In most implementations dynamically allocated objects take up slightly more space than auto objects. And dynamic memory to the best of my knowledge is rarely quicker.

But many implementations limit the size of the stack (where auto variables are usually allocated).

[Edwin van den Oetelaar]

Since the factorial of 100 is a constant, do not calculate it.
Use a lookup table for constants.
Best solution for speed, code and memory optimization.
Have a happy day,
Edwin

PS, spell check is broken?

[BartC]

"Edwin van den Oetelaar" <newsg...@oetelaar.com> wrote in message
news:4fb4dda2$0$30630$6d5e...@onsnet.xlned.com...

> On 05/13/2012 05:42 PM, ashu wrote:
>> Dear Friends,
>> i need to know how to calculate big numbers i.e. factorial of 100. i
>> google and found a solution but didn`t understand how it is done.and
>> some others solution is using some library .but i actually want to
>> develop a solution witch i understand. kindly give me some logic?
>> atleast i need to know how to start with.
>> thankx
>
> Since the factorial of 100 is a constant, do not calculate it.
> Use a lookup table for constants.

Please give an example for 100! in C. Then perhaps one for 10000! or
1000000!

See, it's not so easy! You first need to *know* what the answer is. It's
that step we're trying to do.

Also, we don't know exactly which factorial we want; it could be 100!, or it
could be 3531! We need a table of all factorials up to some arbitrary upper
limit.

> Best solution for speed, code and memory optimization.

1000000! has over five million digits. Then you have all the factorials
below 1000000! And all the ones above that, up to our limit. I'm not sure
that's the most optimal way of using memory!

> PS, spell check is broken?

(The spell-checker seems to be working fine.)

--
Bartc

[Nobody]

On Thu, 17 May 2012 02:42:19 -0700, nick_keighley_nospam wrote:

> But many implementations limit the size of the stack (where auto variables
> are usually allocated).

Also, heap allocation failure is usually easier to catch than stack
allocation failure.

[Bl0ckeduser]

On 12-05-17 05:42 AM, nick_keigh...@hotmail.com wrote:
> On Tuesday, May 15, 2012 3:11:45 PM UTC+1, Bl0ckeduser wrote:
>> On 12-05-15 05:37 AM, Noob wrote:
>>> bl0cked...@gmail.com wrote:
>
>>> Declaring "huge" auto arrays is not the best idea.
>>>
>>> You had better allocate such objects dynamically.
>>
>> Good idea. I think a good dynamic allocation scheme
>> would save memory and allow my program to calculate larger
>> factorials much faster.
>
> I don't see why. It's unlikely to save memory. In most implementations dynamically allocated objects take up slightly more space than auto objects. And dynamic memory to the best of my knowledge is rarely quicker.

The reason I thought that is that dynamically allocating only as much as
needed (or roughly as much) instead of allocating 1000000 as I did
originally would save memory if the factorial is not too big. And the
reason I thought it would be faster is that only allocating roughly as
many digits as needed prevents the program from wasting lots of time on
leading zeros in the case of smaller factorials (as it currently does).

Anyways thanks for the advice.

[Joe keane]

In article <pan.2012.05.17....@nowhere.com>,

Nobody <nob...@nowhere.com> wrote:
>Also, heap allocation failure is usually easier to catch than stack
>allocation failure.

If you are writing code that is supposed to be reliable, it's much
better. Check for no-mem, if so, clean up and report 'we're sorry, we
are unable to fulfill your request at this time'; or get SEGV...

well great now you screwed up the shared memory too

...

So this one time, some customer had a problem, they were running
thousands of threads and their requirements for stack were tight.

Then i found the problem:

int smash_page(PAGE *page)
{
PAGE tmppage;

...(page, tmppage)...

memcpy(page, &tmppage, sizeof PAGE);
}

Perfectly sensible, but when i switched it to use heap their problem
fixed itself. I confirmed that the run-time was negligible.

For multi-thread, heap memory needs as much memory as is needed at one
time, while stack memory needs as much memory as all of them will need
at some time.