New Big Integer library is almost finished

[ad1mt]

Mparith is different in that the size of the BigInteger grows as needed and is not of fixed size, that can be an advantage as you don't have to worry about overflow

That can also be a disadvantage, as Marcel Martin notes.
Suppose you accidentally write a program that goes into an inifinite loop, and it only stops when OS memory runs out. Having overflow would then be useful.
And if your program has been installed by 1000 or 10,000 users, even more so.

[MathMan]

...

I discovered the bugs while investigating the speed difference between the "fast track" and "long track" paths.
I still don't understand reason for the big speed difference. I will keep looking.

Hi ad1mt,

I'm afraid you'll not understand the speed difference by looking at the sources alone. There is an influence from the underlying mathematics of the division. Put very simple it is this

 - when you do a 'fast track' division the individual 32 bit quotients are correct, so no corrections need to be made
 - when you do a 'slow track' division the individual 32 bit quotients may be 1 or 2 too large and costly corrections have to be made <= correction means you add back the divisor, positionally correct, and decrement the 32 bit quotient by 1
 - the way you calculate the individual 32 bit quotient needs a single correction in 1 out 3 cases and a double correction in 1 out of 100 cases

The above is a description how it works in the long division algorithms I know. I really tried to find the related parts in you long division routine - I think the above is handled at label 9000, but I'm not entirely sure.

Kind regards,
MathMan

[ad1mt]

I'm afraid you'll not understand the speed difference by looking at the sources alone.

I agree 100%.
This is why I was had so many problems getting the Knuth algorithm to work. I orignally translated the C code to Pascal code, line by line, without understanding the logic/method. Then when it didn't work, I was completely unable to fix my Pascal code version.

It was only after I "re-engineered" the algortihm with pencil & paper, that understood it; and only then was I able to get the Pascal version working.

In my code, I have a label named "AGAIN", which used I deliberately, to match the C code version from Henry Warren's "Hacker's Delight". It's the code that loops back to this label that does the corrections you mention.

[srvaldez]

I had a look at the C code that you mentioned, in several places he has expressions like (un[i + 1] << 16 - s) , the C compiler warned me to use parentheses and understandably so, the above should be written as (un[i + 1] << (16 - s))

[ad1mt]

@ad1mt, please try the following version, try each arctan formulas, why is the second formula about 22 times slower ?
it's this term that takes a very long time ArcTanInv(T,96,12943)

I've just made version 4.71 available.
It has performance improvements, and minor bug fixes.
The second formula ArcTanInv(T,96,12943) is now slightly faster (as Mathman suggested it should be). However, to get the most out of the improvements, you need to define all the integers as 32bit instead of 64bit in your example program.

[srvaldez]

👍

[ad1mt]

I should add that version 4.71 only has the improvements made to some functines of the Multi_Int_XV type. Other types/functines will follow shortly, once the algorithms have been thoroughly tested.

[ad1mt]

I've temporarily reverted back to version 4.70 on Git, because of bugs. A fixed version will be available soon.

[ad1mt]

I've just made version 4.72 available.
It has speed improvements, but this time done correctly.
It also has bug fixes and some code tidy up.

[srvaldez]

thank you ad1mt 👍

[ad1mt]

I've just made version 4.73 available.
This has speeded-up subtract function, and bug fixes.
There is also a new version of the unit test program.

You people must think I'm an idiot!  A never-ending series of bug fixes on a piece of code that I never seem to be able to get correct.

[ad1mt]

thank you ad1mt 👍

I'm looking forward to getting your next test program!  You always seem to be able to find bugs that I've missed!

[srvaldez]

multi-precision arithmetic is fascinating to me, I have been playing with my own MP floating-point for some years and found that simple meaningless tests can stress test and expose bugs 

[ad1mt]

multi-precision arithmetic is fascinating to me

For a long time, it was fascinating to me too.
But now it's becoming a bit tiresome.

[Fibonacci]

Code: Pascal  [Select][+][-]

1. program app;
2.  
3. uses Multi_Int;
4.  
5. procedure test1;
6. var
7.   i: Int32;
8.   m: Multi_Int_X3;
9. begin
10.   writeln('# Int32 (signed)');
11.   // assign highest possible signed int
12.   i := high(integer);    
13.   writeln('i    = ', i:11);
14.   // and overflow it
15.   i += 1;        
16.   writeln('i +1 = ', i:11);
17.  
18.   writeln;
19.                
20.   writeln('# Multi_Int_X3 (?)');
21.   // assign highest possible signed int
22.   m := high(integer);  
23.   writeln('m    = ', m.ToStr:11);
24.   // and overflow it
25.   m += 1;    
26.   writeln('m +1 = ', m.ToStr:11);
27.  
28.   writeln;
29.  
30.   writeln('value correct? ', i = int64(m), ', i = ', i, ', m = ', int64(m));
31.   writeln('bits the same? ', binstr(i, 64) = binstr(int64(m), 64));
32.   writeln('i bits = ', binstr(i, 64));
33.   writeln('m bits = ', binstr(int64(m), 64));
34.   writeln('m bits = ', m.ToBin:64);
35. end;
36.  
37. procedure test2;
38. var
39.   i: Int32;
40. begin
41.   writeln('# Int32');
42.   i := -123;  
43.   writeln('value = ', i);
44.   writeln('bits                   = ', binstr(i, 33), ' value = ', Int64(i):11);
45.   i := -123;
46.   i := i xor (1 shl 31);
47.   writeln('bits xored without ABS = ', binstr(i, 33), ' value = ', Int64(i):11);
48.   i := -123;
49.   i := abs(i);
50.   i := i xor (1 shl 31);
51.   writeln('bits xored    with ABS = ', binstr(i, 33), ' value = ', Int64(i):11);
52. end;
53.  
54. procedure test3;
55. var
56.   i: Multi_Int_X3;
57. begin
58.   writeln('# Multi_Int_X3');
59.   i := -123;
60.   writeln('value = ', i.ToStr);
61.   writeln('bits                   = ', i.ToBin:33, ' value = ', Int64(i):11); // using Int64 because of overflow
62.   i := -123;
63.   i := i xor (1 shl 31);
64.   writeln('bits xored without ABS = ', i.ToBin:33, ' value = ', Int64(i):11);
65.   i := -123;
66.   i := abs(i);
67.   i := i xor (1 shl 31);
68.   writeln('bits xored    with ABS = ', i.ToBin:33, ' value = ', Int64(i):11);
69. end;
70.  
71. procedure test4;
72. var
73.   i: Multi_Int_X3;
74. begin
75.   writeln('# Multi_Int_X3');
76.   writeln('# cast to Int64 before converting to binary');
77.   i := -123;
78.   writeln('value = ', i.ToStr);
79.   writeln('bits                   = ', binstr(int64(i), 33):33, ' value = ', Int64(i):11); // using Int64 because of overflow
80.   i := -123;
81.   i := i xor (1 shl 31);
82.   writeln('bits xored without ABS = ', binstr(int64(i), 33):33, ' value = ', Int64(i):11);
83.   i := -123;
84.   i := abs(i);
85.   i := i xor (1 shl 31);
86.   writeln('bits xored    with ABS = ', binstr(int64(i), 33):33, ' value = ', Int64(i):11);
87. end;
88.  
89. begin
90.   writeln('****** test 1 ******');
91.   test1;
92.   writeln;
93.   writeln;
94.  
95.   writeln('****** test 2 ******');
96.   test2;
97.   writeln;
98.   writeln;
99.  
100.   writeln('****** test 3 ******');
101.   test3;
102.   writeln;
103.   writeln;
104.  
105.   writeln('****** test 4 ******');
106.   test4;
107.   writeln;
108.   writeln;
109.  
110.   readln;
111. end.

Code: Text  [Select][+][-]

1. ****** test 1 ******
2. # Int32 (signed)
3. i    =  2147483647
4. i +1 = -2147483648
5.  
6. # Multi_Int_X3 (?)
7. m    =  2147483647
8. m +1 =  2147483648
9.  
10. value correct? FALSE, i = -2147483648, m = 2147483648
11. bits the same? TRUE
12. i bits = 0000000000000000000000000000000010000000000000000000000000000000
13. m bits = 0000000000000000000000000000000010000000000000000000000000000000
14. m bits =                                 10000000000000000000000000000000
15.  
16.  
17. ****** test 2 ******
18. # Int32
19. value = -123
20. bits                   = 011111111111111111111111110000101 value =        -123
21. bits xored without ABS = 001111111111111111111111110000101 value =  2147483525
22. bits xored    with ABS = 010000000000000000000000001111011 value = -2147483525
23.  
24.  
25. ****** test 3 ******
26. # Multi_Int_X3
27. value = -123
28. bits                   =                          -1111011 value =        -123
29. bits xored without ABS = -10000000000000000000000001111011 value = -2147483771
30. bits xored    with ABS =  10000000000000000000000001111011 value =  2147483771
31.  
32.  
33. ****** test 4 ******
34. # Multi_Int_X3
35. # cast to Int64 before converting to binary
36. value = -123
37. bits                   = 111111111111111111111111110000101 value =        -123
38. bits xored without ABS = 101111111111111111111111110000101 value = -2147483771
39. bits xored    with ABS = 010000000000000000000000001111011 value =  2147483771

I guess I just dont know how to use it.