[SOLVED] Need help converting a C++ math program

[jamie]

Wanted to let every one know that something I forgot about between C and Pascal.

Bitwise operators in C calculate the complete operands on both sides, left and right including those of - +, not just *

In Pascal that isn't the case.

For example:

10 - 1 shl 3 = 2 in pascal, 72 in C

so if you have something like this.

 10 shl 1 + 1; that would be  10 shl (1+1) in C but (10 shl 1)+1 in pascal.

[Zvoni]

Wanted to let every one know that something I forgot about between C and Pascal.

Bitwise operators in C calculate the complete operands on both sides, left and right including those of - +, not just *

In Pascal that isn't the case.

For example:

10 - 1 shl 3 = 2 in pascal, 72 in C

so if you have something like this.

 10 shl 1 + 1; that would be  10 shl (1+1) in C but (10 shl 1)+1 in pascal.

Reading the docs helps
C++: https://en.cppreference.com/w/cpp/language/operator_precedence.html
Pascal: https://www.freepascal.org/docs-html/ref/refch12.html

You can see clearly:
in C++ shift Left/Right comes after addition/subtraction
in pascal before

[jamie]

Well, that's a nice chart and all but, it does not explain the issue I found.

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

1.  1 shl 1+1 = 3  //in pascal, or at least in Fpc, i haven't checked Delphi.
2.  1 << 1+1 = 4 //in c
3.  

You see what I mean, the chart does not explain this from what i can see.

and the same holds true if this one on the left side.

I suspect that maybe even things like the MOD operator ( maybe doing the same .

[creaothceann]

The charts do explain it, it means:

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

1. (1 shl 1) + 1 -->  3  // Pascal
2. 1 << (1 + 1)  -->  4  // C
3.  

(And that's why I always put parentheses in my code, so that I don't have to remember the operator precedence tables.)

[jamie]

Maybe in your eyes it does, to me it only explains where the operators are on the priority list which makes sense to me but it's not doing well on showing what happens to the Operands final value to be used in the operators in quetion.

  All +,-,/ etc are all on the lower list, that only tells me what Pascal (Fpc) is playing it.


 its a good thing I have a C++ compiler sitting here to verify this, this isn't the first time I've ran into this porting C code, and I can't determine who is wrong/right here?

Jamie

[srvaldez]

jamie
are you testing your code in 64-bit or 32-bit?
if in 64-bit then try in 32-bit

[MathMan]

Maybe in your eyes it does, to me it only explains where the operators are on the priority list which makes sense to me but it's not doing well on showing what happens to the Operands final value to be used in the operators in quetion.

  All +,-,/ etc are all on the lower list, that only tells me what Pascal (Fpc) is playing it.


 its a good thing I have a C++ compiler sitting here to verify this, this isn't the first time I've ran into this porting C code, and I can't determine who is wrong/right here?

Jamie

This one explains it - I used it a lot while I translated the original C++ source to FPC first time

https://en.cppreference.com/w/cpp/language/operator_precedence.html

Beside that, and out of curiosity, did you verify that the C++ version is actually working? You have a C++ compiler, which I don't.

[440bx]

You have a C++ compiler, which I don't.

Have you tried some of the online C++ compilers ?  That could be helpful if they can compile the code you're translating.

[srvaldez]

good day Mr. MathMan 
here's a working C version of NTT, there are two C versions one using for loops and the other using while loops
 

[creaothceann]

to me it only explains where the operators are on the priority list which makes sense to me but it's not doing well on showing what happens to the Operands final value to be used in the operators in quetion [...] All +,-,/ etc are all on the lower list, that only tells me what Pascal (Fpc) is playing it

C has the + and - operators above the shift operators, so they're evaluated first. It's like putting parantheses around the operands that are to the left and right of the operator.

[PascalDragon]

I think when 3.3.x comes out it should also advanced the GVector and those like it to use the Anonymous Functions so functions like All_OF, None etc can be implemented.

Well, then someone will have to provide that. If someone wants improvements for fcl-stl then it needs to come from outside.

[jamie]

@mathMan

 Yes, I do have a C++ compiler, 3 different ones to be exact.

I tested beween gcc, builder and VC++  and all three evaluate the left and right operands fully for a << >> without closures.

 the Shl Shr etc in fpc do not, you need to encapsulate the operands for that to happen.

 I did put the ntt header and test code in the gcc and it seems to pass. Not sure about VC++ or builder, I didn't try those, just small console test lines.

 Also, the __BUILTIN_CTZ in gcc returns 32 for a 0 parameter instead of the 255 or shortInt like Fpc does with the bsfDword for a 0 content.
 

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

1. function TNTT.BUILTIN_CTZ(aValue: U32):Uint32;
2. begin
3.   Result := bsfDWord(aValue);
4.   if shortint(Result) = -1 then
5.   Result := 32; //GCC's output for a zero value.
6. end;                                      
7.  

That works the same as gcc.
jamie

[MathMan]

I'm getting closer. Installed a C compiler and made a debugging tour de force.

The issue is the reduce function. It looks as follows in C and Pascal

Code: C  [Select][+][-]

1.     template <bool strict = true>
2.     u32 reduce(u64 val) const {
3.         u32 res = val + u32(val) * n_inv * u64(mod) >> 32;
4.         if constexpr (strict)
5.             res = shrink(res);
6.         return res;
7.     }

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

1. function reduce(
2.   const val: u64;
3.   const strict: boolean=TRUE
4. ):u32;inline;
5.  
6. begin
7.   Result := ( val + u32( val )*mt.n_inv*u64( mt.mod1 ) ) shr 32;
8.   if( strict ) then
9.     Result := shrink( Result );
10. end;

If the functions are entered with strict=false val=$000000006F1BF78C n_inv=$3B7FFFFF and mod=$3b800001 then the result is

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

1. Pascal: $19D30000
2. C: $23fffff8

I already tried several modifications to the Pascal version, but I can't see how the C result could be generated 

[jamie]

How are you generating the "n_inv" in the constructor ?

This is what I do to avoid the overflow and range check.

With the value of 3 as the input, n_inv should look like this
$5555555555 etc.

I did not put a break point on the c version to varify that but it should be the same.

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

1. constructor TMontgomery.Create(acmod: u32);
2. var
3.   i: integer;
4.   n_inv: u64; //Local large holder.
5. begin
6.   Cmod := acmod; //iitialize the base value;
7.   n_inv := 1;
8.   assert(Cmod mod 2 = 1);
9.   assert(Cmod < (1 shl 30));
10.   cmod2 := 2 * cmod;
11.  
12.   for i := 0 to 4 do
13.     n_inv *= U64(2) + n_inv * u64(cmod);
14.   Self.n_inv := u32(n_inv);  //Put it back to u32 in global space
15.   r := (1 shl 32) mod cmod;
16.   r2 := (r * r) mod cmod;
17. end;                                              
18.  

[MathMan]

@jamie

I just checked, that C and Pascal calculated the same value for n_inv - both had n_inv=$3b7fffff for the mo=$3b80001.