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

[Thaddy]

Ahum. Why do you use a var e, where the const e (Euler's number) may be in scope?
It is probably working for you and not illegal, but especially in math settings: not a good idea. It can lead to confusing code if the const e is defined in one of your units.

[MathMan]

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

The "anything" applies - whether "exactly" also applies I can only tell if you'd show the associated 'mul', 'reduce' & 'shrink'. Did you make that function yourself or is it part of a larger lib (or something) where I could take a look?

There is at least a difference to the 'power' implemented in the C source that I'm looking at - the first mul is <strict> in your case where it is not in my case.

[MathMan]

Ahum. Why do you use a var e, where the const e (Euler's number) may be in scope?
It is probably working for you and not illegal, but especially in math settings: not a good idea. It can lead to confusing code if the const e is defined in one of your units.

The task at hand is to have a Pascal source as close as possible to the C source, including variable names.

When/if I get this running it will receive my usual re-work with reasonable naming etc.

[LV]

This is not my sport; it’s just an attempt.
I'm also an amateur programmer. 

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

1. testing _mod: 3
2.  
3. testing _mod: 5
4.  
5. testing _mod: 17
6.  
7. testing _mod: 257
8.  
9. testing _mod: 65537
10.  
11. testing _mod: 1000000007
12.  
13. testing _mod: 1000000009
14.  
15. testing _mod: 1000001329
16.  
17. testing _mod: 998244353
18.  
19. All tests passed!
20.  

[MathMan]

@LV

Many thanks - the output looks promising. If this really works (will test) then I only have to understand where I stumbled with my own implementation.

[MathMan]

@LV

Sorry, but it is not working. Your tests just passed, because nothing was tested at all - variable 'lg'=0 throughout the complete test.

In addition the ntt.create generates no twiddle-factor tables due to a similar issue and if I start ntt.conv then procedure 'DoStep' terminates with an access violation due to that.

Nevertheless - thanks for your support. I'll see how it behaves when I correct the obvious errors.

[jamie]

@MathMan

 I have the ntt header translated, i need to complete the test apo, i got tired 

Ill complete it later after i varify all translTions working.

[jamie]

I haven't forgot about you @MathMan 

Been working a little on it and debugging and have discovered the MIN function from the Math lib does not return negitive values if the smallest is in the - range, what I mean is, the binary conversion does not flip the bits into what would normally be
a -number but zeros it out on the results.

At least that is what the debugger is showing.

Also, the use of bsfDword does not follow to what the C++ specs it out as so I made a little local function to correct the results of that making it more compatible.

The bsfDword function will return 255 for all on bits and 0 for the first bit. it appears the C version wants it different.

basically the __BUILTIN_CTX function.

 More on this later.

Jamie

[MathMan]

I haven't forgot about you @MathMan 

Been working a little on it and debugging and have discovered the MIN function from the Math lib does not return negitive values if the smallest is in the - range, what I mean is, the binary conversion does not flip the bits into what would normally be
a -number but zeros it out on the results.

At least that is what the debugger is showing.

Also, the use of bsfDword does not follow to what the C++ specs it out as so I made a little local function to correct the results of that making it more compatible.

The bsfDword function will return 255 for all on bits and 0 for the first bit. it appears the C version wants it different.

basically the __BUILTIN_CTX function.

 More on this later.

Jamie

I thought about these two too. However, changing x := min( x,y ) to x := x-y*UInt32( x>=y ) doesn't improve the situation and for the second case an input of 0 or 2^32-1 for BsfDWord seems logically impossible.

[srvaldez]

please don't shoot me
I combined the C++ code and added parentheses around the << and >> expressions to make it un-ambiguous, saved it as ntt-2.cpp
I compiled it and compared it with the unmodified C++ code and the relevant parts matched, I then asked deep seek to translate the code to Free Pascal
can you translate the following C++ code to Free Pascal, please map u32 → UInt32 and u64 → UInt64?
unfortunately the code won't compile but I thought that it might be of interest to you

[Thaddy]

That it not compiles is simply because the type restriction to boolean, which is not possible and will likely never be possible.
What will be possible in the future is type restrictions to ordinals of which boolean is a manifestation.

[jamie]

@mathman
I made a BUILTIN_CTZ function using the bsfdword to correct for the results.
 Also the min func issue i had was the debugger, i had to be at 0 op to correct that.

 Currently i am getting a prime number not found in the find.... etc
More later

[jamie]

as I am tinkering about this app, I've notice, especially in the BudderFyy_x2 function where I got a range error, yes I do use things once in a while! it's like not reading the assembly instructions!

 Anyways, I probe in there, checking values on the variables and the debugger shows me
 
$DEADBEEF. Then I found one next to it, $DEADBEEF0

can anyone explain that?

Jamie

[MathMan]

as I am tinkering about this app, I've notice, especially in the BudderFyy_x2 function where I got a range error, yes I do use things once in a while! it's like not reading the assembly instructions!

 Anyways, I probe in there, checking values on the variables and the debugger shows me
 
$DEADBEEF. Then I found one next to it, $DEADBEEF0

can anyone explain that?

Jamie

Re the range errors: All this is arithmetics modulo 2^32 and at various places range errors are simply accepted. I think I placed a {$Q-}{$R-} at the top with an explanation towards that.

Re the $deadbeef: afaic this is a 'space filler' used by FPC. In which data structure did you see it?

MathMan

[jamie]

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

1. procedure TNTT.transform_aux(inverse, trival: longbool; k, i: integer;
2.   Data: Pu32; var wi: u32; constref mt: TMontgomery);
3. {$PointerMath on}
4. var
5.   j: integer;
6. begin
7.   for j := 0 to (1 shl k) - 1 do
8.    Try
9.      butterfly_x2(inverse, trival, Data[i + j], Data[i + (1 shl k) + j], wi, mt);
10.    except
11.      Beep;
12.    end;
13.   wi := mt.mul(True, wi, ifThen<TVector32>(inverse, wrd,
14.     wd).Items[BUILTIN_CTZ(not (i) shr k + 1)]);
15. end;                                                        
16.  
17.  

Well, it appears that i+j are creating indexes outside the allocated space in the TVector, so it must be a some values getting set incorrectly.
 
 So the Data[ i+j ].//// is generating an index into the map of the vector outside its allocated items range.

Also the BUILTIN_CTZ is generating a value that exceeds the items list because the NOT(i) is generating a range issue.

But I am taking this from the C source code as is.
lots of fun