Recent

Author Topic: Big Numbers Math  (Read 558 times)

woodybrison

  • Newbie
  • Posts: 6
Big Numbers Math
« on: March 26, 2024, 12:59:07 am »
I've created a method for handling huge numbers, perhaps it might be useful to someone else. Maybe someone can find an error in it...

I was up against a problem: in a set of 1 million elements, how many ways can they be paired? The first el could be paired with 999,999 other choices. For each of those, the 2nd el could be paired with 999,997 other choices, so 999,999 x 999,997 x 999,995 x ... x 1. There would be a half million pairs:

     499,999
      ∏ 999999-2i  = ?
     i=0

Wolfram/Alpha was unable to compute this.

I wondered if Free Pascal could do it.

Free Pascal's largest type (that I know of) is Extended, with a max value of 1.1x10^4932.

I set up a type with separate mantissa (an Extended) and exponent (a uint64).

type bignum = record mant :Extended; expn :uint64; end;

This might be more useful if the exponent be a signed int64 so it could handle very small numbers also.

To multiply two such numbers, you add the exponents and multiply the mantissas, and if the mantissas' product is larger than some limit you divide it by ten and add one to the exponent.

The program below computes the above product. I ran a test, shown at the end of the program - that worked; and I followed the output, it looks correct. The answer it computes is:

     499,999
      ∏ 999999-2i  ≈  8.12014 x 10^2782852
     i=0

This seems to be correct. It is smaller than 1M^500K, which is 10^3M.

The program took 1 second to finish on a 2 GHz Pentium.

Code: Pascal  [Select][+][-]
  1. Program bigmath;
  2. // handles very large numbers
  3.  
  4. type
  5.   bignum = record
  6.     mant :Extended;
  7.     expn :uint64;
  8.     end;
  9.  
  10. var
  11. //  AA, BB, prod :bignum;  // test
  12.   i :uint32;
  13.   accum, multiplier :bignum;
  14.  
  15. //====================================
  16. procedure adjust( var X :bignum );
  17.   begin
  18.   while X.mant >= 10 do
  19.     begin
  20.     X.mant /= 10;
  21.     inc( X.expn );
  22.     end;
  23.   end;
  24.  
  25. //====================================
  26. function multiply( A,B :bignum ) :bignum;
  27.   var temp :bignum;
  28.   begin
  29.   temp.mant := 1;
  30.   temp.expn := 0;
  31.   temp.mant := A.mant * B.mant;
  32.   temp.expn := A.expn + B.expn;
  33.   adjust( temp );
  34.   exit( temp );
  35.   end;
  36.  
  37. //=============== MAIN ===============
  38. begin
  39. accum.mant := 1;  // accumulates the product
  40. accum.expn := 0; //  set it to 1 to begin with
  41.  
  42. for i := 0 to 499999 do
  43.   begin
  44.   multiplier.mant := 999999-2*i;
  45.   multiplier.expn := 0;
  46.   adjust( multiplier );
  47.  
  48.   accum := multiply( accum, multiplier );
  49.  
  50.   // tracking progress:
  51.   if (i < 50) or (i > 499949) or (i mod 500 = 0) then
  52.     writeln( i:7, ' acc=', accum.mant:0:5, 'x10^', accum.expn,
  53.              ' multi=', multiplier.mant:0:5, 'x10^', multiplier.expn );
  54.   end;
  55.  
  56. // displaying the final answer:
  57. writeln( '        acc=', accum.mant:0:5, 'x10^', accum.expn,
  58.          ' multi=', multiplier.mant:0:5, 'x10^', multiplier.expn, ' <====' );
  59. end.
  60.  
  61. // test: 999,999 * 999,997 = 999996000003
  62. //
  63. // AA.mant := 999999;
  64. // AA.expn := 0;
  65. // BB.mant := 999997;
  66. // BB.expn := 0;
  67. // prod := multiply( AA, BB );
  68. // write( AA.mant:0:0, 'x10^', AA.expn,
  69. //  ' x ', BB.mant:0:0, 'x10^', BB.expn,
  70. //  ' = ', prod.mant:0:19, 'x10^', prod.expn );
  71. //
  72. // test result
  73. // 999999x10^0 x 999997x10^0 = 9.9999600000300024000x10^11
  74. // note the round-off error creeping up
  75.  
« Last Edit: Today at 01:28:31 am by woodybrison »

AlexTP

  • Hero Member
  • *****
  • Posts: 2387
    • UVviewsoft
Re: Big Numbers Math
« Reply #1 on: March 26, 2024, 05:08:41 am »
Why not to use forum CODE tag for the code block?

woodybrison

  • Newbie
  • Posts: 6
Re: Big Numbers Math
« Reply #2 on: Today at 01:30:21 am »
I plead ignorance. Now I've put the tags in. I had to snuffle around a bit to find out how. My only motive here is the help the universe.

Thaddy

  • Hero Member
  • *****
  • Posts: 14210
  • Probably until I exterminate Putin.
Re: Big Numbers Math
« Reply #3 on: Today at 07:22:49 am »
Well, the notation seems a good idea, but note there are many good biginteger - and so by extension through scaling also floats - for Object Pascal. Even one or two in the standard distribution. Their range is usually in principle infinite at the cost of being exponentially very slow.
Specialize a type, not a var.

 

TinyPortal © 2005-2018