Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #20757 > unrolled thread

working with big numbers

Back to article view | Back to comp.lang.c

Contents

  working with big numbers ashu <ashishmourya21@gmail.com> - 2012-05-13 08:42 -0700
    Re: working with big numbers thomas.mertes@gmx.at - 2012-05-13 09:48 -0700
      Re: working with big numbers Ike Naar <ike@sverige.freeshell.org> - 2012-05-15 07:19 +0000
        Re: working with big numbers Nils M Holm <news2009@t3x.org> - 2012-05-15 07:56 +0000
          Re: working with big numbers Ike Naar <ike@sverige.freeshell.org> - 2012-05-15 14:11 +0000
    Re: working with big numbers thomas.mertes@gmx.at - 2012-05-13 10:00 -0700
    Re: working with big numbers Barry Schwarz <schwarzb@dqel.com> - 2012-05-14 15:53 -0700
    Re: working with big numbers bl0ckedusersoft@gmail.com - 2012-05-14 13:11 -0700
      Re: working with big numbers Noob <root@127.0.0.1> - 2012-05-15 11:37 +0200
        Re: working with big numbers Bl0ckeduser <bl0ckedusersoft@gmail.com> - 2012-05-15 10:11 -0400
          Re: working with big numbers nick_keighley_nospam@hotmail.com - 2012-05-17 02:42 -0700
            Re: working with big numbers Nobody <nobody@nowhere.com> - 2012-05-17 18:43 +0100
              Re: working with big numbers jgk@panix.com (Joe keane) - 2012-05-18 21:57 +0000
            Re: working with big numbers Bl0ckeduser <bl0ckedusersoft@gmail.com> - 2012-05-17 17:44 -0400
      Re: working with big numbers Peter Nilsson <airia@acay.com.au> - 2012-05-16 15:38 -0700
        Re: working with big numbers Bl0ckeduser <bl0ckedusersoft@gmail.com> - 2012-05-16 22:01 -0400
    Re: working with big numbers Paul <nospam@needed.com> - 2012-05-14 19:44 -0400
    Re: working with big numbers Robert Miles <robertmilesxyz@gmail.com> - 2012-05-14 18:16 -0700
    Re: working with big numbers Ike Naar <ike@sverige.freeshell.org> - 2012-05-15 06:50 +0000
    Re: working with big numbers Nils M Holm <news2009@t3x.org> - 2012-05-15 07:06 +0000
    Re: working with big numbers James Dow Allen <jdallen2000@yahoo.com> - 2012-05-15 02:13 -0700
      Re: working with big numbers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-05-15 11:07 +0100
        Re: working with big numbers Nils M Holm <news2009@t3x.org> - 2012-05-15 11:10 +0000
          Re: working with big numbers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-05-15 15:03 +0100
            Re: working with big numbers Bl0ckeduser <bl0ckedusersoft@gmail.com> - 2012-05-15 10:34 -0400
    Re: working with big numbers Edwin van den Oetelaar <newsgroups@oetelaar.com> - 2012-05-17 13:14 +0200
      Re: working with big numbers "BartC" <bc@freeuk.com> - 2012-05-17 12:34 +0100

Page 1 of 2  [1] 2  Next page →

#20757 — working with big numbers

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

[toc] | [next] | [standalone]

#20758

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.

[toc] | [prev] | [next] | [standalone]

#20787

On 2012-05-13, thomas.mertes@gmx.at <thomas.mertes@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.

[toc] | [prev] | [next] | [standalone]

#20790

Ike Naar <ike@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.

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

[toc] | [prev] | [next] | [standalone]

#20806

On 2012-05-15, Nils M Holm <news2009@t3x.org> wrote:
> Ike Naar <ike@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.

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.

[toc] | [prev] | [next] | [standalone]

#20759

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. 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

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 ----------


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.

[toc] | [prev] | [next] | [standalone]

#20771

On Sun, 13 May 2012 08:42:42 -0700 (PDT), ashu
<ashishmourya21@gmail.com> 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.

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

[toc] | [prev] | [next] | [standalone]

#20772

On Sunday, May 13, 2012 11:42:42 AM UTC-4, 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

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

[toc] | [prev] | [next] | [standalone]

#20792

bl0ckedusersoft@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.

[toc] | [prev] | [next] | [standalone]

#20807

On 12-05-15 05:37 AM, Noob wrote:
> bl0ckedusersoft@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.

[toc] | [prev] | [next] | [standalone]

#20879

On Tuesday, May 15, 2012 3:11:45 PM UTC+1, Bl0ckeduser wrote:
> On 12-05-15 05:37 AM, Noob wrote:
> > bl0ckedusersoft@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). 

[toc] | [prev] | [next] | [standalone]

#20921

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.

[toc] | [prev] | [next] | [standalone]

#21006

In article <pan.2012.05.17.17.43.13.654000@nowhere.com>,
Nobody  <nobody@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.

[toc] | [prev] | [next] | [standalone]

#20939

On 12-05-17 05:42 AM, nick_keighley_nospam@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:
>>> bl0ckedusersoft@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.

[toc] | [prev] | [next] | [standalone]

#20867

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

[toc] | [prev] | [next] | [standalone]

#20871

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.

[toc] | [prev] | [next] | [standalone]

#20773

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

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

[toc] | [prev] | [next] | [standalone]

#20776

On Sunday, May 13, 2012 10:42:42 AM UTC-5, 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

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.

[toc] | [prev] | [next] | [standalone]

#20785

On 2012-05-13, ashu <ashishmourya21@gmail.com> 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

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.

[toc] | [prev] | [next] | [standalone]

#20786

ashu <ashishmourya21@gmail.com> wrote:
> 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

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

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c

csiph-web