Super Large Integer Math Calculations

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Super Large Integer Math Calculations

noreply
For integers beyond 64 bit, or even beyond 32 bit on a 64 bit machine,
why can't the math be broken down into peices the way a human does it on
paper, and then theoretically any number can be added and subtracted,
even if it is beyond 32/64 bit?

Example:

type TSuperLargeInt = string;

var
   i, j: TSuperLargeInt;
   output: TSuperLargeInt;
begin
   i := '100000000000000000009';
   j := '100000000000000000001';
   output := AddLargeInts(i,j);
   writeln(output);
end.

The function AddLargeInts simply breaks the math into peices and adds 9
plus one, carries the one, then adds 1 plus 1, and writes the total as a
string,, that the computer can output as a string, instead of an integer
the cpu can handle directly. Strings allow concatenations of numbers to
virtually any length (with the limit of the max string length, which is
quite long) so when you use math to write numbers as strings, the number
can be written any length you want.

And it doesn't have to be strings that are used, but some compiler magic
that uses strings internally (concatenating numbers and writing
numbers). Strings can be used as a prototype to prove the concept
works... (I can provide a demo if needed).

Am I reinventing something that already exists somewhere in, the Math
unit, or elsewhere, to have math operations on super large numbers
beyond 32/64 bit?

This just covers addition/subtraction, which can be broken down into
small pieces an int32 can easily handle (you are simply doing math from
0-9 numbers, so its byte sized math!) - multiplication can likely be
broken down into small pieces too but I haven't thought about it.

Surely someone has already thought of this and it exists somewhere?

To add the two large numbers above, simple write a function that:
  - adds the last number (9) and 1 in the string, and carries any
remainder
  - adds the second last number, with the remainder, so result is 1
  - adds the third last...
  -  etc..
  - up until the first number (1)
  - write the output result as a concatenated/constructed string (not
int32)

AFAICT any large number to ridiculous size limits can be added by
breaking the math into small pieces that 32 bit numbers can handle (or
rather byte sized numbers actually since you are doing 0-9 math
addition).

This has got to be reinventing the wheel though: someone must have
already invented this in Fortran or the math unit, or somewhere...?

And then the question becomes, what math cannot be done, by breaking
down into small byte sized pieces.

Loops: not sure if these super large integers are any good in loops
unless you loop an int32 around several times (compiler magic?).

The reason I use a simple case of adding 100000000000000000009 with
another number is for simple test case that doesn't require much
thought.. obviously 9 plus 1 means 10, so you carry the 1. then the rest
is easy since you skip all the zeros and add the first 1 and 1 = 2. But
the point is, addition on paper by humans is broken down to 0-9
additions, so why not a CPU can do this too? Then output the result as a
concatenated string even if the cpu cannot hold this number directly
since it is bigger than int32.

Possibly I may be reinventing this:
http://www.delphiforfun.org/Programs/Library/big_integers.htm
Quote "All operations are performed pretty much the way you would do
them with pencil and paper."

And:
http://rvelthuis.de/programs/bigintegers.html

A compiler could have magic inside it, or a unit could use operator
overloading, to make it more built in and not use strings, but some
custom type (maybe implemented as a string underneath, or array of
bytes). Surely fortran or a number crunching language must have thought
of this already, or the freepascal Math unit, or some BigInteger unit
out there already.

Interesting Turing test: can all math be done up until infinity, on an
int32 computer, if you just implement compiler magic to work around your
int32 limitation, and break it down to byte sized (or int32 sized)
pieces...
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Super Large Integer Math Calculations

Bart-48
On 7/7/17, [hidden email] <[hidden email]> wrote:

> For integers beyond 64 bit, or even beyond 32 bit on a 64 bit machine,
> why can't the math be broken down into peices the way a human does it on
> paper, and then theoretically any number can be added and subtracted,
> even if it is beyond 32/64 bit?
>
> Example:
>
> type TSuperLargeInt = string;
>
> var
>    i, j: TSuperLargeInt;
>    output: TSuperLargeInt;
> begin
>    i := '100000000000000000009';
>    j := '100000000000000000001';
>    output := AddLargeInts(i,j);
>    writeln(output);
> end.

http://svn.code.sf.net/p/flyingsheep/code/trunk/wtf/ncalc.pp does exactly that
(all dependenies are also found at
http://svn.code.sf.net/p/flyingsheep/code/trunk/wtf).

It can handle integers (and only integers) up to 2GB digits with
absolut precision.
It can handle GoogolPlex.

Calculate 9^99 with absolute precision:
29512665430652752148753480226197736314359272517043832886063884637676943433478020332709411004889

Fac(100)?
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

It's not lightning fast, but there is room for optimization I guess.

Bart
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Super Large Integer Math Calculations

Ingemar Ragnemalm
In reply to this post by noreply

Bart <[hidden email]> wrote:

> On 7/7/17, [hidden email] <[hidden email]> wrote:
>
>> For integers beyond 64 bit, or even beyond 32 bit on a 64 bit machine,
>> why can't the math be broken down into peices the way a human does it on
>> paper, and then theoretically any number can be added and subtracted,
>> even if it is beyond 32/64 bit?
>>
>> Example:
>>
>> type TSuperLargeInt = string;
>>
>> var
>>     i, j: TSuperLargeInt;
>>     output: TSuperLargeInt;
>> begin
>>     i := '100000000000000000009';
>>     j := '100000000000000000001';
>>     output := AddLargeInts(i,j);
>>     writeln(output);
>> end.
> http://svn.code.sf.net/p/flyingsheep/code/trunk/wtf/ncalc.pp does exactly that
> (all dependenies are also found at
> http://svn.code.sf.net/p/flyingsheep/code/trunk/wtf).
>
> It can handle integers (and only integers) up to 2GB digits with
> absolut precision.
> It can handle GoogolPlex.
>
> Calculate 9^99 with absolute precision:
> 29512665430652752148753480226197736314359272517043832886063884637676943433478020332709411004889
>
> Fac(100)?
> 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
>
> It's not lightning fast, but there is room for optimization I guess.
>
> Bart

Great! I knew someone must have made that! I needed this a few months
ago, but resorted to Python at that time. Now I can use FPC next time. :)

/Ingemar

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Super Large Integer Math Calculations

noreply
In reply to this post by Bart-48
On 2017-07-07 17:08, Bart wrote:

> On 7/7/17, [hidden email] <[hidden email]> wrote:
>
>> For integers beyond 64 bit, or even beyond 32 bit on a 64 bit machine,
>> why can't the math be broken down into peices the way a human does it
>> on
>> paper, and then theoretically any number can be added and subtracted,
>> even if it is beyond 32/64 bit?
>>
>> Example:
>>
>> type TSuperLargeInt = string;
>>
>> var
>>    i, j: TSuperLargeInt;
>>    output: TSuperLargeInt;
>> begin
>>    i := '100000000000000000009';
>>    j := '100000000000000000001';
>>    output := AddLargeInts(i,j);
>>    writeln(output);
>> end.
>
> http://svn.code.sf.net/p/flyingsheep/code/trunk/wtf/ncalc.pp does
> exactly that
> (all dependenies are also found at
> http://svn.code.sf.net/p/flyingsheep/code/trunk/wtf).
...

> It's not lightning fast, but there is room for optimization I guess.
>
> Bart

I knew someone had already invented this!
Any idea if it does square roots, and, decimal point numbers too..

Or, what math can it "not" do.. things like sin/tan/cos, or strange
maths..

Probably a complex question requiring a complex answer

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Super Large Integer Math Calculations

Stuart Cox

Have a look at http://www.wolfgang-ehrhardt.de/


On 2017-07-11 6:05 AM, [hidden email] wrote:
On 2017-07-07 17:08, Bart wrote:
On 7/7/17, [hidden email] [hidden email] wrote:

For integers beyond 64 bit, or even beyond 32 bit on a 64 bit machine,
why can't the math be broken down into peices the way a human does it on
paper, and then theoretically any number can be added and subtracted,
even if it is beyond 32/64 bit?

Example:

type TSuperLargeInt = string;

var
   i, j: TSuperLargeInt;
   output: TSuperLargeInt;
begin
   i := '100000000000000000009';
   j := '100000000000000000001';
   output := AddLargeInts(i,j);
   writeln(output);
end.

http://svn.code.sf.net/p/flyingsheep/code/trunk/wtf/ncalc.pp does exactly that
(all dependenies are also found at
http://svn.code.sf.net/p/flyingsheep/code/trunk/wtf).
...

It's not lightning fast, but there is room for optimization I guess.

Bart

I knew someone had already invented this!
Any idea if it does square roots, and, decimal point numbers too..

Or, what math can it "not" do.. things like sin/tan/cos, or strange maths..

Probably a complex question requiring a complex answer

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal


_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Super Large Integer Math Calculations

noreply
On 2017-08-10 22:45, Stuart Cox wrote:
> Have a look at http://www.wolfgang-ehrhardt.de/
>


Thanks, looks interesting!

I could not find the maximum supported length of a number (multi
gigabyte?) or number string though..

i.e. for big numbers, but how big? Big is a vague term :-)

It might be mentioned somewhere on his pages, I just couldn't find it
yet
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Super Large Integer Math Calculations

noreply
On 2017-08-20 16:29, I previously wrote:

> On 2017-08-10 22:45, Stuart Cox wrote:
>> Have a look at http://www.wolfgang-ehrhardt.de/
>>
>
>
> Thanks, looks interesting!
>
> I could not find the maximum supported length of a number (multi
> gigabyte?) or number string though..
>
> i.e. for big numbers, but how big?

On his page, I found this:

"For 32/64-bit compilers MAXDigits should be <= 2^24"

http://www.wolfgang-ehrhardt.de/mp_intro.html
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Loading...