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

[MathMan]

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

Ok, then let's pause it here for the moment.

I'll translate again from scratch taking all your hints & suggestions into consideration to get Pascal code as close as possible to the C source. Will take a day or two and we resume from there?

[MathMan]

good day Mr. MathMan
I apologize if you know this already, I don't mean to insult you
I ran test.cpp a number of times and the results don't match between runs, unless you are able to tweak the cpp code to give the same results between runs I don't see how you are going to verify your pascal translation

Hello srvaldez,

Actually I didn't know - I don't have a C compiler to check. I thought that it was verified by the author, as there is a test program associated to it (which I also packed in my initial post). Could you check that, maybe?

If the C source really doesn't work then this changes everything ...


Forget the above, I was to hasty in my response. The question is if check.cpp passes or fails. That the values change between runs may well be possible, if C++ RTL does not provide repeatable random sequences, as FPC RTL does.

[MathMan]

<snip>

Ok, then let's pause it here for the moment.

I'll translate again from scratch taking all your hints & suggestions into consideration to get Pascal code as close as possible to the C source. Will take a day or two and we resume from there?

@Zvoni - to the best of my abilities I made a second attempt, staying close to the original C source. Pls take a look.

Thanks,
MathMan

[440bx]

More general comments about porting C code to Pascal...

Before I even start porting the C code, I compile it and ensure it works correctly.  There is no point in porting something that doesn't work.

One thing as a result of the above step is that I always have debuggable C code.  That way if the Pascal port isn't working, I can place breakpoints in strategic places in both executables and verify values match.  A mismatch gives an idea of where things are going wrong.

If the code relies on some random numbers, I will hard code matching "random number" values in the C and Pascal code.  Repeatability is important and, often a necessity when things aren't working as expected.  In extreme cases, even memory addresses can be made repeatable and synchronized between the two apps by inserting a custom memory manager in both executables.  This is rarely needed but, can be extremely useful when it is needed to find the cause of one or more discrepancies.

Summary: try as much as possible to make the "environment" where the C and Pascal executables run to be as close as possible to being the same.   That can save a lot of time and aggravation.

HTH.

[Thaddy]

if C++ RTL does not provide repeatable random sequences, as FPC RTL does.

What makes you think that? C++ can even produce the same sequence as FPC 3.2.X if mt19937 is specified.
From my wikii entry:

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

1. #include <iostream>
2. #include <random>
3. using namespace std;
4.  int main()
5. {
6.     mt19937 mt_rand(5489u);
7.     for(int i=0;i<5;i++){
8.     cout << mt_rand() << endl;};
9.  
10.     return 0;
11. }

The above code produces - given the same seed - the exact same sequence as FPC 3.2.X does.
C++ PRNG's are pluggable.
For trunk you need xoshiro** to make it fpc compatible since fpc changed its prng.

(I have C++ code that extends <random> with an xoshiro128_starstar engine, but since it is not pascal: if you need that I'll attach it)

[Zvoni]

@Zvoni - to the best of my abilities I made a second attempt, staying close to the original C source. Pls take a look.

Thanks,
MathMan

Now this looks much better..

Though:

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

1. var
2.   n: u32;
3.   i: u32;
4.   f: u32;
5.  
6.   Index: UInt32;  // not in C source: need this to emulate std::vector.push_back
7.  
8.   Check: boolean; // not in C source: need this to emulate std::vector.all_of
9.   Count: UInt32;  // not in C source: need this to emulate std::vector.all_of
10.  
11.   factors: array of u32;

?!?!?!?!?!
https://www.freepascal.org/daily/packages/fcl-stl/gvector/tvector.html

Include Unit "Gvector".....

[Thaddy]

One caveat with C++ vs FreePascal math is that C++ can cast float values directly to its bit-pattern, whereas Fpc has a value so needs an extra cast to obtain the bit-pattern of a float value. This can be quite confusing and since bit-patterns are used a lot in C++ math, very important to be aware of during translations. Most Pascal programmers do it wrong the first time. (That included me in the past)

[MathMan]

<snip>

Though:

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

1. var
2.   n: u32;
3.   i: u32;
4.   f: u32;
5.  
6.   Index: UInt32;  // not in C source: need this to emulate std::vector.push_back
7.  
8.   Check: boolean; // not in C source: need this to emulate std::vector.all_of
9.   Count: UInt32;  // not in C source: need this to emulate std::vector.all_of
10.  
11.   factors: array of u32;

?!?!?!?!?!
https://www.freepascal.org/daily/packages/fcl-stl/gvector/tvector.html

Include Unit "Gvector".....

I wasn't aware this existed. Now I looked into it and this is generics stuff - with which I had no acquaintance so far. I'm afraid I might introduce more errors if I include this. Beside that it seems to miss the iterator std::vector.all_of so it's only half the show, isn't it?

Pls understand - I'm a hobby programmer. And all my programs so far are strictly procedural, because my playfield does not require more and is geared towards efficiency.

[Zvoni]

I wasn't aware this existed. Now I looked into it and this is generics stuff - with which I had no acquaintance so far. I'm afraid I might introduce more errors if I include this. Beside that it seems to miss the iterator std::vector.all_of so it's only half the show, isn't it?

Pls understand - I'm a hobby programmer. And all my programs so far are strictly procedural, because my playfield does not require more and is geared towards efficiency.

Considering "all_of" is not a Member of "vector" but of "std"

https://en.cppreference.com/w/cpp/container/vector.html
https://en.cppreference.com/w/cpp/algorithm/all_any_none_of.html

[MathMan]

<snip>

Considering "all_of" is not a Member of "vector" but of "std"

https://en.cppreference.com/w/cpp/container/vector.html
https://en.cppreference.com/w/cpp/algorithm/all_any_none_of.html

You're right, I mixed it up. I gave gvector a try - 'find_pr_root' now looks like

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

1. function find_pr_root(
2.   mod1: u32;
3.   constref mt: tMontgomery
4. ):u32;
5.  
6. type
7.   tFactors = specialize tVector<u32>;
8.  
9. var
10.   n: u32;
11.   i: u32;
12.   f: u32;
13.  
14.   Check: boolean; // not in C source: need this to emulate std::all_of
15.  
16.   factors: tFactors;
17.  
18. begin
19.   Result := 0;
20.   factors := tFactors.Create;
21.  
22.   n := mt.mod1 - 1;
23.   i := 2;
24.   while( ( u64( i )*i )<=n ) do begin
25.     if( ( n mod i )=0 ) then begin
26.       factors.PushBack( i );
27.       repeat
28.         n := n div i;
29.       until( ( n mod i )<>0 );
30.     end;
31.  
32.     Inc( i );
33.   end;
34.  
35.   if( n>1 ) then begin
36.     factors.PushBack( n );
37.   end;
38.  
39.   i := 2;
40.   while( i<mod1 ) do begin
41.     Check := TRUE;
42.     for f in factors do begin
43.       Check := Check and ( power( i, ( mt.mod1-1 ) div f, FALSE, FALSE )<>1 );
44.     end;
45.     if( Check=TRUE ) then Exit( i );
46.  
47.     Inc( i );
48.   end;
49.  
50.   Assert( FALSE, 'primitive root not found' );
51. end;

What do you think?

[jamie]

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.

 But you can do that in a for loop but not using the "IN" operator so you can use the BREAK in the check and then afterwards check to see if the Index counter for the loop made it all the way.

Jamie

[Zvoni]

<snip>

Considering "all_of" is not a Member of "vector" but of "std"

https://en.cppreference.com/w/cpp/container/vector.html
https://en.cppreference.com/w/cpp/algorithm/all_any_none_of.html

You're right, I mixed it up. I gave gvector a try - 'find_pr_root' now looks like

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

1. function find_pr_root(
2.   mod1: u32;
3.   constref mt: tMontgomery
4. ):u32;
5.  
6. type
7.   tFactors = specialize tVector<u32>;
8.  
9. var
10.   n: u32;
11.   i: u32;
12.   f: u32;
13.  
14.   Check: boolean; // not in C source: need this to emulate std::all_of
15.  
16.   factors: tFactors;
17.  
18. begin
19.   Result := 0;
20.   factors := tFactors.Create;
21.  
22.   n := mt.mod1 - 1;
23.   i := 2;
24.   while( ( u64( i )*i )<=n ) do begin
25.     if( ( n mod i )=0 ) then begin
26.       factors.PushBack( i );
27.       repeat
28.         n := n div i;
29.       until( ( n mod i )<>0 );
30.     end;
31.  
32.     Inc( i );
33.   end;
34.  
35.   if( n>1 ) then begin
36.     factors.PushBack( n );
37.   end;
38.  
39.   i := 2;
40.   while( i<mod1 ) do begin
41.     Check := TRUE;
42.     for f in factors do begin
43.       Check := Check and ( power( i, ( mt.mod1-1 ) div f, FALSE, FALSE )<>1 );
44.     end;
45.     if( Check=TRUE ) then Exit( i );
46.  
47.     Inc( i );
48.   end;
49.  
50.   Assert( FALSE, 'primitive root not found' );
51. end;

What do you think?

hmm... don't like Line 41 and following
Yes, you need to emulate the "all_of".
Everything else looks good.
Don't forget to Free "Factors" (you created it in Line20)

[jamie]

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

1. procedure TForm1.Button1Click(Sender: TObject);
2. Type
3.   TV = TVector<Integer>;
4. Var
5.   V:TV;
6.   I:Integer;
7. begin
8.  V := TV.Create;
9.  For I := 1 to 10 do
10.   V.PushBack(Random(123)); //Create a fake list of items first for test;
11.  For I := 0 To V.Size-1 do
12.    If (V.Items[I] >0)and(V.Items[I]<50) Then Break;
13.  if I < V.Size Then Beep; // if I < V.Size then it means the loop broke out early.
14.  V.Free;
15. end;                                  
16.  

That is how you scan and exit early in the loop and then check if the loop completed!

P.S.

 I just corrected the last line for a check of completeness of the FOR LOOP.
 This can be implemented to scan the contents of the Vector and do some checks on it so those
 Items like All_OF etc can be emulated simply.

Jamie

[MathMan]

<snip>

hmm... don't like Line 41 and following
Yes, you need to emulate the "all_of".
Everything else looks good.
Don't forget to Free "Factors" (you created it in Line20)

I made further analysis and I'm now convinced it is the 'power' function that is not working correct. It tries to calculate modular powers in Montgomery space with input either from Euclidean or Montgomery space - providing output either in Euclidean or Montgomery. This seems to be handled incorrect. It's not impossible to do, just tricky as forward/backward conversion and specific reduction has to be applied carefully.

Have to look at the math to understand how to correct this.

[jamie]

Does it look anything like this

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

1. function TMontgomery.power(input_in_space, output_in_Space: longbool; b, e: u32): u32;
2. var
3.   r: u32 = 0;
4. begin
5.   if not (input_in_space) then
6.     b := mul(strikt, b, r2);
7.   if output_in_space then R := Self.R
8.   else
9.     r := 1;
10.   while (e > 0) do
11.   begin
12.     if (e and 1) <> 0 then
13.       r := mul(False, r, b);
14.     b := mul(False, b, b);
15.     e := e shr 1;
16.   end;
17.   Result := shrink(r);
18. end;                                  
19.  
20.  

jamie