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

[MathMan]

Hello all,

I'm experiencing issues with translating a C++ program to Pascal - both attached. The issue is that the computed results are incorrect. To gain some insights I already deconstructed the templated C++ source fully, so the Pascal source currently is not the most beautiful. I implemented minor changes - for which I verified that they have no effect on the calculation

* I replaced std:min... with a different construct, as FPC RTL min (in Math) is handling parametrisation different
* I replaced the constant product 'n_inv*mod' with a precomputed value 'Base'
* in some functions I optimised the array access

Here's what I already know

* it is not an issue of optimisation levels - results are consistend (though wrong) through O0-O4
* it is not an issue of inlining - again results are consistend under {$inline on} and {$inline off}

I suspect the issue resides in the 'PwrMod' variants (or functions used by that), because

* 'FindPrimRoot' already delivers a wrong result (i.e. '2', which is not a primitive root of the choosen modulus) and this one only uses 'PwrModxx'
 
After fiddling with this for five days now I thought I'd ask for help, because my understanding of C++ is limited - and the issue seems to be something intricate that is constantly escaping my eye.

Many thanks,
MathMan

[Zvoni]

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

1. Montgomery() = default;
2.     /* snip */
3.         for (int i = 0; i < 5; i++) {
4.             n_inv *= 2 + n_inv * mod;
5.         }
6.        /* snip */
7.     }

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

1. for Count := 0 to 5 do begin
2.     NegInv := NegInv * ( 2+NegInv*Mod1 );
3.   end;

Spot at least the first mistake....

[MathMan]

Hello Zvoni,

Why do you think the translation is in error? C defines that for '[operator]=' statements the right hand side is first calculated fully and then the operator is applied.

I at least verified that 'UInt32( NegInv*Mod1 )=UInt32( -1 )' holds for the calculated NegInv - so I don't think this is incorrect. I also looked at calculations in the two 'Reduce' statements that use NegInv. The calculations always come out with 0 for the least significant 32 bit there - this is expected in a Montgomery multiplication.

But thanks for taking the time to look into.

Cheers,
MathMan

[Zvoni]

Hello Zvoni,

Why do you think the translation is in error? C defines that for '[operator]=' statements the right hand side is first calculated fully and then the operator is applied.

I at least verified that 'UInt32( NegInv*Mod1 )=UInt32( -1 )' holds for the calculated NegInv - so I don't think this is incorrect. I also looked at calculations in the two 'Reduce' statements that use NegInv. The calculations always come out with 0 for the least significant 32 bit there - this is expected in a Montgomery multiplication.

But thanks for taking the time to look into.

Cheers,
MathMan

The C++-Loop executes 5 times,
your Pascal Loop executes 6 times....

[dseligo]

Hello Zvoni,

Why do you think the translation is in error? C defines that for '[operator]=' statements the right hand side is first calculated fully and then the operator is applied.

I at least verified that 'UInt32( NegInv*Mod1 )=UInt32( -1 )' holds for the calculated NegInv - so I don't think this is incorrect. I also looked at calculations in the two 'Reduce' statements that use NegInv. The calculations always come out with 0 for the least significant 32 bit there - this is expected in a Montgomery multiplication.

But thanks for taking the time to look into.

Cheers,
MathMan

The C++-Loop executes 5 times,
your Pascal Loop executes 6 times....

I've always hated this C (C++) loops. It's so unreadable to me: I always have to think about that condition, and if it is compared before or after increasing counter.

[Zvoni]

I've always hated this C (C++) loops. It's so unreadable to me: I always have to think about that condition, and if it is compared before or after increasing counter.

https://www.w3schools.com/cpp/cpp_for_loop.asp

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

1.  for (statement 1; statement 2; statement 3) {
2.   // code block to be executed
3. }

Statement 1 is executed (one time) before the execution of the code block.

Statement 2 defines the condition for executing the code block.

Statement 3 is executed (every time) after the code block has been executed.

The Pitfall is more the "For"-Keyword
A "For"-Loop in C/C++ is actually more like a While-Loop in Pascal
A "For"-Loop in Pascal (For i:=0 To 5 Do) is INCLUSIVE of the boundaries ("0" AND "5") and calculated once, then cached (enough discussions on this forum)

His code in "correct" translation would be (untested)

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

1. Count:=0;
2. While Count<5 Do
3. Begin
4.   NegInv := NegInv * ( 2+NegInv*Mod1 );
5.   Inc(Count);
6. End;

Though i agree, it can be written as a For-Loop in Pascal, since in the C++-Code the iterator is never "accessed"

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

1.     for Count := 0 to 4 do NegInv := NegInv * ( 2+NegInv*Mod1 );

[MathMan]

Ah, now I get your point, thanks.

Unfortunately it doesn't change a jota on the result, as the calculation of NegInv is convergent to a fixpoint and any loop iteration above 5 simply gives the same result :-)

Nevertheless I changed the loop to

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

1.   for Count := 0 to 4

[Zvoni]

Ah, now I get your point, thanks.

Unfortunately it doesn't change a jota on the result, as the calculation of NegInv is convergent to a fixpoint and any loop iteration above 5 simply gives the same result :-)

Nevertheless I changed the loop to

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

1.   for Count := 0 to 4

Well, i did say "first mistake" since i didn't expect that one to be the only culprit, though i haven't looked at the rest, yet

he next thing i don't like:
you use a variable "base" in your Init-Function

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

1. Base := UInt64( NegInv ) * UInt64( Mod1 );

But in the C++-code it's a multiplication of an U32 with U64 and then Right Shifts.

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

1. /* snip */
2. u32 n_inv;
3. /* snip */
4. u32 reduce(u64 val) const {
5.         u32 res = val + u32(val) * n_inv * u64(mod) >> 32;
6.         if constexpr (strict)
7.             res = shrink(res);
8.         return res;

I don't expect it to make a difference, but i just don't like it

The same with

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

1. r2 = u64(r) * r % mod;

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

1. RmndS := ( UInt64( Rmnd )*UInt64( Rmnd ) ) mod Mod1;

[Zvoni]

Next:

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

1. while( ( Norm mod Dvsr )=0 ) do begin
2.         Norm := Norm div Dvsr;
3.       end;

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

1. do {
2.                     n /= i;
3.                 } while (n % i == 0);

The C++-Code is a Repeat..Until-Loop, because it runs at least ONCE, while a WHILE-Loop might run zero times

btw: Why in blazes do you use different Variable-Names?!?!?
Use the same Variable-Names in your Pascal-Code as in the C++-Code
it's a PITA "translating" in my head

And why do you have (redundant) code for the C++-Templates?
Took me a while to figure out, what it means.
If you don't want to use Generics (though i don't know if it's even possible with generics), just add one/two more boolean-Arguments to your Function(s)

[MathMan]

Next:

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

1. while( ( Norm mod Dvsr )=0 ) do begin
2.         Norm := Norm div Dvsr;
3.       end;

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

1. do {
2.                     n /= i;
3.                 } while (n % i == 0);

The C++-Code is a Repeat..Until-Loop, because it runs at least ONCE, while a WHILE-Loop might run zero times

btw: Why in blazes do you use different Variable-Names?!?!?
Use the same Variable-Names in your Pascal-Code as in the C++-Code
it's a PITA "translating" in my head

And why do you have (redundant) code for the C++-Templates?
Took me a while to figure out, what it means.
If you don't want to use Generics (though i don't know if it's even possible with generics), just add one/two more boolean-Arguments to your Function(s)

Some answers to the above and to your previous post

* 'Base' doesn't make a difference - I confirmed that (already stated in my initial post)

* the seemingly redundant 'UInt64()' stem from me trying to be on the save side - FPC has auto-expansion to the size available on the target architecture. As this may get compiled for a 32 bit target architecture i expanded both values to the size of 'Base'. Beside that the shift left applies to the full 'Val + UInt32( Val )*Base' - i explicitely looked that up in C reference operator precedence info.

* I changed the loop to a repeat-style, as it removes one mod operation as you correctly noted.

* I want my sources finally to be readable, and for me that includes meaningful variable names. Unfortunately I issued my plea for help in the middle of translations.

* regarding the splitting of the templated C functions - I did that during debugging, as I hoped to gain some more insight. I'm aware that it could be implemented similar in FPC, but there is also the question of exec-speed looming in the background.

[440bx]

General comments, nothing specific.

I very commonly port C code to Pascal and I've learned the hard way that it pays to make the first attempt as parallel to the C code as possible.  IOW, no renaming variables, no improving anything, just make it as one-to-one as possible.  Make it work and, thoroughly test it that way. 

Once it has been thoroughly tested and it really works as intended then and only then "Pascalize" the code.  I've learned it saves a lot of aggravation (and time) to do it in two steps than attempting to do it in one.

Of course, for really simple programs (such as Petzold's C examples), the first step need not be strictly adhered to but, for anything that goes beyond the trivial, it pays to be "religious" about it.

HTH.

[Zvoni]

*snip*
* I want my sources finally to be readable, and for me that includes meaningful variable names. Unfortunately I issued my plea for help in the middle of translations.
*snip*

That's what "Source - Refactoring - Rename Identifier" is for....

EDIT...and quoting 440bx:

it pays to make the first attempt as parallel to the C code as possible.  IOW, no renaming variables, no improving anything, just make it as one-to-one as possible.

Exactly what i'm talking about.

Nevermind OP should use the ctypes-unit.

Though, back to the Issue:
In his pas-file, I see a Unit in Uses and an Include-Directive

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

1. Uses LongArith;
2.  
3. {$include LongCalc.inc}

Never heard of those.... maybe those are the Culprit?

[MathMan]

General comments, nothing specific.

I very commonly port C code to Pascal and I've learned the hard way that it pays to make the first attempt as parallel to the C code as possible.  IOW, no renaming variables, no improving anything, just make it as one-to-one as possible.  Make it work and, thoroughly test it that way. 

Once it has been thoroughly tested and it really works as intended then and only then "Pascalize" the code.  I've learned it saves a lot of aggravation (and time) to do it in two steps than attempting to do it in one.

Of course, for really simple programs (such as Petzold's C examples), the first step need not be strictly adhered to but, for anything that goes beyond the trivial, it pays to be "religious" about it.

HTH.

After this experience I will stick to that too, I think.

Though - I have converted substantial amounts of C to Pascal before and never experienced issues like this before. But there always is a first time 

[MathMan]

*snip*
* I want my sources finally to be readable, and for me that includes meaningful variable names. Unfortunately I issued my plea for help in the middle of translations.
*snip*

That's what "Source - Refactoring - Rename Identifier" is for....

EDIT...and quoting 440bx:

it pays to make the first attempt as parallel to the C code as possible.  IOW, no renaming variables, no improving anything, just make it as one-to-one as possible.

Exactly what i'm talking about.

Nevermind OP should use the ctypes-unit.

Though, back to the Issue:
In his pas-file, I see a Unit in Uses and an Include-Directive

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

1. Uses LongArith;
2.  
3. {$include LongCalc.inc}

Never heard of those.... maybe those are the Culprit?

As stated before, I think I learned my lesson.

Regarding the uses & include - you won't find them anywhere. But I thought you might have a point and removed them - no change, still wrong.

[Zvoni]

As stated before, I think I learned my lesson.

Regarding the uses & include - you won't find them anywhere. But I thought you might have a point and removed them - no change, still wrong.

Well, then....
... don't forget the "ctypes"-Unit.
When porting C/C++ code you should definitely use those types, and not the native Pascal-Types