Integer maths > 16 bits

[MathMan]

I'd suggest Zero128, Unity128 and AllBits128.

At present I'm using the L and H forms, because we know that the compiler will object if the endianess changes. I'm hoping at some point to crank up my surviving SPARC system which will allow a bigendian test...

MarkMLl

Sounds good. I integrated the following into the Int128Types unit interface section

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

1. // some constants often used in mathematics
2. const
3. {$ifdef ENDIAN_BIG}
4.   Zero128:    tUInt128 = ( H:UInt64( 0 ); L:UInt64( 0 ) );
5.   Unity128:   tUInt128 = ( H:UInt64( 0 ); L:UInt64( 1 ) );
6.   AllBits128: tUInt128 = ( H:High( UInt64 ); L:High( UInt64 ) );
7. {$else}
8.   Zero128:    tUInt128 = ( L:UInt64( 0 ); H:UInt64( 0 ) );
9.   Unity128:   tUInt128 = ( L:UInt64( 1 ); H:UInt64( 0 ) );
10.   AllBits128: tUInt128 = ( L:High( UInt64 ); H:High( UInt64 ) );
11. {$endif}
12.  

[MarkMLl]

I'll probably post the test code I'm using tomorrow. It applies a fairly naive hashing algorithm to a passphrase for a number of word sizes (originally 16 and 32 bits, now also 64 and 128) and then tries to find the nearest prime to the result... obviously this is slow when word size is large.

Obviously during startup I'm running testcases, and Near128Prime(0) highlights that it would be useful to be able to suppress range/overflow checks when crossing zero. Apart from that there's the missing mod operator (which can be easily refined locally).

I've not given any thought to the extent to which this might be useful to people working with IPv6. I've previously found myself "jumping through hoops" with v4 (i.e. 32-bit) addresses, again with things like inc/dec through zero for an arbitrary subnet size: I don't know whether v6 has comparable concepts.

MarkMLl

[MathMan]

I'll probably post the test code I'm using tomorrow. It applies a fairly naive hashing algorithm to a passphrase for a number of word sizes (originally 16 and 32 bits, now also 64 and 128) and then tries to find the nearest prime to the result... obviously this is slow when word size is large.

If you would also show the source of Near128Prime I'd take a look at that too. I assume that function takes a considerable amount of the overall execution, especially in the 128 bit case. There are some pretty interesting detection algorithms out there - but I'd first have to deep-dive into the math. So /if/ I can speed that up then it will take some time.

Obviously during startup I'm running testcases, and Near128Prime(0) highlights that it would be useful to be able to suppress range/overflow checks when crossing zero. Apart from that there's the missing mod operator (which can be easily refined locally).

If you only need mod for unsigned types then I can add that pretty fast.

Cheers,
MathMan

[MarkMLl]

If you would also show the source of Near128Prime I'd take a look at that too. I assume that function takes a considerable amount of the overall execution, especially in the 128 bit case. There are some pretty interesting detection algorithms out there - but I'd first have to deep-dive into the math. So /if/ I can speed that up then it will take some time.

If you only need mod for unsigned types then I can add that pretty fast.

Compilable project before the end of tomorrow. Unsigned mod would be entirely OK, possibly also Odd() which should be another easy one.

MarkMLl

[MathMan]

If you would also show the source of Near128Prime I'd take a look at that too. I assume that function takes a considerable amount of the overall execution, especially in the 128 bit case. There are some pretty interesting detection algorithms out there - but I'd first have to deep-dive into the math. So /if/ I can speed that up then it will take some time.

If you only need mod for unsigned types then I can add that pretty fast.

Compilable project before the end of tomorrow. Unsigned mod would be entirely OK, possibly also Odd() which should be another easy one.

MarkMLl

Ok, I'll start with mod. Look for 'IsOdd' it's already there - now that I look at it I can't remember why I named it that way. Especially as I declared it as 'overload' which would hint as me trying to overload it to the RTL function, which however is 'odd' 

MathMan

[MarkMLl]

Ok, I'll start with mod. Look for 'IsOdd' it's already there - now that I look at it I can't remember why I named it that way. Especially as I declared it as 'overload' which would hint as me trying to overload it to the RTL function, which however is 'odd' 

Just been bitten by that one: tried to define Odd(ow) as Odd(ow.L) and couldn't stop the code from going recursive.

The "nearby primes" are definitely the local CPU gluttons. However I think it's a fair thing to ask a computer to do, particularly when generating a key from a passphrase... fortunately that's the sort of thing that a host computer could probably do rather than having a limited-resource embedded system exerting itself.

I think the local mathemagicians could have a bit of fun with this :-)

Added: At present I've got separate functions for the various previous/next/nearest primes because I wanted no ambiguity at all when it came to wrapping through zero. I'm obviously aware that this is a candidate for being implemented as generics once they're fully documented etc., although things like IsOdd() vs Odd() and special per-type wraparound handling will complicate it.

MarkMLl

[MathMan]

Progress on my side:

 - now there is 'mod' for unsigned types, including unit tests and integration into the benchmark utility
 - 'IsOdd' / 'IsEven' got replaced by 'Odd' / 'Even'. I now remember why I named them different initially. I do see them as value query not value modification functions and that should be reflected in the function name, like 'IsZero', 'IsPowOf2', 'Is DivisibleBy' ... But I admit, though grudingly  , that they are used ubiquituous for this purpose as 'Odd' / 'Even'.

Further things on my list
 - I consider implementing 'DivMod' which would return quotient and remainder from a single calculation. As often both values are needed in concert that might be worth the effort to implement. Your take?
- I'd like to clean up on the signed types 'div' and 'mod' operators. But I'm unsure about the direction. Issue is - the way FPC calculates these for ordinal types is mathematically incorrect. Should I now go for the 'correct' implementation or continue the 'used too' to 128 bit? This is a question also to everybody else who happens to read this thread, or has downloaded my first version of the library - I know there are some.

Cheers,
MathMan

[Thaddy]

- I consider implementing 'DivMod' which would return quotient and remainder from a single calculation. As often both values are needed in concert that might be worth the effort to implement. Your take?

Yes, please: I use divmod a lot for all kind of purposes. ( although for my purposes I doubt if I need a big integer library for that.)
Basically processing a value in chunks (div) and then process the remainder (mod). Would be nice to have it thread safe.

[MathMan]

- I consider implementing 'DivMod' which would return quotient and remainder from a single calculation. As often both values are needed in concert that might be worth the effort to implement. Your take?

Yes, please: I use divmod a lot for all kind of purposes. ( although for my purposes I doubt if I need a big integer library for that.)

Noted, thanks for the feedback Thaddy. Remember in this thread we only talk about 128 bit math - not arbitrary precision.

Basically processing a value in chunks (div) and then process the remainder (mod). Would be nice to have it thread safe.

Uhm, thread safety wasn't on my agenda so far as this is only 128 bit math and I'm not sure about use cases that would need thread safety here. We can take that offline I guess - PM me please.

MathMan

[MarkMLl]

Uhm, thread safety wasn't on my agenda so far as this is only 128 bit math and I'm not sure about use cases that would need thread safety here. We can take that offline I guess - PM me please.

Thanks for the comment Thaddy, I was hoping you were still here since I'm out of my depth when it comes to the theory.

My prime code appears to work for 128 bits, albeit slowly (will have relative timing later). I'm considering adding a thread for the nearest-prime stuff, since "is the number n steps below the starting point prime" and "is the number n steps above the starting point prime" could obviously be run in parallel. However (short of finding a better primality test, for which I am not qualified) I think the major improvement would be replacing my existing "either side by steps of two" with something wheel-like: look at the starting number mod 6 and tailor the step pattern to that.

I'll post my existing demo code as soon as I have timing... hopefully later albeit with an unfixed bug in a debugging dump procedure which is normally unused.

MarkMLl

[MarkMLl]

With all range checks etc. enabled and no optimisation:

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

1. $ time ./Hash16Demo-x86_64-linux
2. Internal check: passphrase hashing passed
3. 835B 1000001101011011 8
4.  
5. real    0m0.002s
6. user    0m0.002s
7. sys     0m0.000s
8.  
9. $ time ./Hash32Demo-x86_64-linux
10. Internal check: passphrase hashing passed
11. 12D63C37 00010010110101100011110000110111 16
12.  
13. real    0m0.002s
14. user    0m0.002s
15. sys     0m0.000s
16.  
17. $ time ./Hash64Demo-x86_64-linux
18. Internal check: passphrase hashing passed
19. 4A450DC7E3D890BF 0100101001000101000011011100011111100011110110001001000010111111 32
20.  
21. real    0m7.260s
22. user    0m7.260s
23. sys     0m0.000s
24.  
25. $ time ./Hash128Demo-x86_64-linux
26. Internal check: passphrase hashing passed
27. An unhandled exception occurred at $000000000047A135:
28. EIntOverflow: multiply tUInt128 by UInt64
29.   $000000000047A135  star,  line 2699 of ../../int128/int128.pas
30.   $000000000046C3E8  HASH128PASSPHRASE,  line 453 of HashCommon.pas
31.   $0000000000401A2E  main,  line 23 of Hash128Demo.lpr
32.   $000000000042DD10  SYSENTRY,  line 141 of system.pp
33.  
34. real    556m5.141s
35. user    555m54.503s
36. sys     0m1.984s
37.  

That successfully demonstrates that the internal tests work, which include hashing a short passphrase and finding the nearest prime.

I believe that the exception was in the actual test program, when it was looking at a somewhat larger test passphrase. Other than the difficulty of telling the library to wrap on overflow, that's my problem so I attach the relevant files below.

There's a project group (.lpg) file which can in effect be ignored. For each of the test programs- using 16-, 32-, 64- and 128-bit integers, there's a .lpi plus a .lpr. The .lpr mostly defines macros then includes a .inc, that can confuse Lazarus and/or FPC on occasion so if in doubt force a full rebuild.

Enjoy  :-)

MarkMLl

[MarkMLl]

- I'd like to clean up on the signed types 'div' and 'mod' operators. But I'm unsure about the direction. Issue is - the way FPC calculates these for ordinal types is mathematically incorrect. Should I now go for the 'correct' implementation or continue the 'used too' to 128 bit? This is a question also to everybody else who happens to read this thread, or has downloaded my first version of the library - I know there are some.

This is awkward: strictly, it should depend on the compiler mode of the calling code which is probably unavailable.

MarkMLl

[MarkMLl]

I think it might be necessary to have some way of passing "out of band" state to the library, and this would definitely need to be thread-safe.

The exception I commented on earlier appears to be caused by overflow checks being enabled at the project level, so when Int128 was compiled with overflow checks enabled at the project level mandatory exceptions were built in: they can't be disabled by {$q- } at the point of invocation.

So while for operands of <= 64 bits this works:

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

1.   for i := 1 to Length(pp) do begin
2. {$push }
3. {$rangechecks off}
4. {$overflowchecks off }
5.     result := result + Ord(pp[i]);
6.     result *= alphabetPrime
7. {$pop  }
8.   end;
9.  

it's ineffective for 128-bit operands.

That implies that it would be useful to have something like PushChecks and PopChecks procedures, plus CheckOverflow and possibly something like CompilerMode so that a caller could tell the library how the mod operator should behave.

Also I think it would be desirable if all exception messages were distinct, even if they were only distinguished by (a), (b) and so on.

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

1.     raise EIntOverflow.create( 'multiply tUInt128 by UInt64' ); // <=====
2.   end else begin
3.     Carry := UMul128by64L( Temp, O1, q );
4.     if( Carry>0 ) then begin
5.       raise EIntOverflow.create( 'multiply tUInt128 by UInt64' ); // <=====
6.  

If even a trivial change had been made to the library since it was last compiled, the exception address could easily be out of step with reality.

[MathMan]

I think it might be necessary to have some way of passing "out of band" state to the library, and this would definitely need to be thread-safe.

The exception I commented on earlier appears to be caused by overflow checks being enabled at the project level, so when Int128 was compiled with overflow checks enabled at the project level mandatory exceptions were built in: they can't be disabled by {$q- } at the point of invocation.

So while for operands of <= 64 bits this works:

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

1.   for i := 1 to Length(pp) do begin
2. {$push }
3. {$rangechecks off}
4. {$overflowchecks off }
5.     result := result + Ord(pp[i]);
6.     result *= alphabetPrime
7. {$pop  }
8.   end;
9.  

it's ineffective for 128-bit operands.

That implies that it would be useful to have something like PushChecks and PopChecks procedures, plus CheckOverflow and possibly something like CompilerMode so that a caller could tell the library how the mod operator should behave.

Also I think it would be desirable if all exception messages were distinct, even if they were only distinguished by (a), (b) and so on.

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

1.     raise EIntOverflow.create( 'multiply tUInt128 by UInt64' ); // <=====
2.   end else begin
3.     Carry := UMul128by64L( Temp, O1, q );
4.     if( Carry>0 ) then begin
5.       raise EIntOverflow.create( 'multiply tUInt128 by UInt64' ); // <=====
6.  

If even a trivial change had been made to the library since it was last compiled, the exception address could easily be out of step with reality.

Let me try to tackle your feedback - not neccessarily in the order given above

- distinguished error messages <= count on me implementing that
- yes, if you compiled the library with range & overflow checks enabled there currently is no way to avoid them becoming active in case.
  - issue is, the lib is a compound object and many of it's operations will not be inlined into the invocation
  - You  surely could compile the lib without checks enabled, but then loose these on all operations - which I understand is not desired
  - the only way around this and support local enable / disable at invocation level is the installation of a thread save execution state var in the lib
  - together with getter/setter functions and a dispatch to operation variants with / without checks this would probably address your requirements
  - however this is a major rework and it will slow down execution speed, so I might have to put a way on top of this for those who don't care
  - all doable, but not in short time frame - and I'd need independent testers. Would you stay in this?
- the handling of div, mod, divmod etc.  is simpler I think - I can install a compile time switch that controls the code generation towards variant A or B

That's my shot from the hip.

Cheers,
MathMan

PS - there might be a better alternative - what do you think about the following

- implement a checked and unchecked type variant and extend the operator overloading accordingly
- if you want to disable checks on the invocation level then you can use the unchecked type for calculations

[MarkMLl]

- implement a checked and unchecked type variant and extend the operator overloading accordingly
- if you want to disable checks on the invocation level then you can use the unchecked type for calculations

Yes, that should work since these are not "well known" types that will be subject to automatic type conversions (something that, over the last few years, I have become increasingly unhappy about).

Could possibly also be used for the "which language mode" issue, particularly since div/mod are probably subject to different problems from plus/multiply/minus.

In the interim, I've put this at the top of int128.pas to decouple the checks it uses internally from the rest of the project.

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

1. {$ifdef CHECK_INT128 }
2.   {$rangechecks on}
3.   {$overflowchecks on }
4. {$else }
5.   {$rangechecks off}
6.   {$overflowchecks off }
7. {$endif }
8.  

I'd also note that I'm defining USE_FPC64 and USE_INT128 at the project level. I might remove the first of those after I've checked the situation on the RPi Pico etc., although that definitely won't be this week.

MarkMLl