Calling hotshot coders: NFS code challenge

[xenon]

Here is a comparison of assembly vs C. This is to give an estimation of the speed gain using assembly, so I haven't comment the assembly code yet.

My method is linking the OBJ file with C code. The benchmarking code is written in C. I use Visual C++ 6.0 and I hope you have no problem compiling it. I haven't prepare to let you look at my assembly code, I admit it is very messy. But you can try using the function

extern "C" __fastcall eegcd(int input, int modulus);

link together with inverse1.obj.
Don't trust my code yet. Check if there is any wrong result produced.

eegcd-11 means Euclidean algorithm with 11 times repeated subtraction.

          eegcd-11 eegcd-10 eegcd-9 eegcd-8 eegcd-7 akruppa_C
 1048583    300      313      310     316    321      418
 2097169    315      326      324     332    333      422
 4194319    316      326      322     332    332      429
 8388617    322      331      328     337    338      437
16777259    333      343      340     350    350      457
33554467    345      355      352     363    363      475

From the looks of it I see a lot of repeated code.
.NET may be the way to go.

xenon

I've compiled it with Visual Studio 6.0.(c++6)
It hangs upon launch, so I didn't get to far with it.
I'm not an expert in C++, but I have dabbled with it.
Although I am more famliar with .NET, which is a love hate relationship.

[xenon]

TTn

When you compile, you should see
... inverse3.cpp(19) : warning C4101: 'temp' : unreferenced local variable
This is expected.

I guess __fastcall didn't work. But for the same compiler, it shouldn't be a problem.
Try replacing
//ans = single_modinv_ak(i, PRIME);
ans = eegcd(i, PRIME);

with
ans = single_modinv_ak(i, PRIME);
//ans = eegcd(i, PRIME);

Also if your computer is less than 1GHz, wait for 10 seconds before killing off the process.
If that doesn't help. Create a new project and try using the akruppa C code first. Then you can sort out the problem.

[R.D. Silverman]

Originally Posted by xenon

Here is a comparison of assembly vs C. This is to give an estimation of the speed gain using assembly, so I haven't comment the assembly code yet.

My method is linking the OBJ file with C code. The benchmarking code is written in C. I use Visual C++ 6.0 and I hope you have no problem compiling it. I haven't prepare to let you look at my assembly code, I admit it is very messy. But you can try using the function

extern "C" __fastcall eegcd(int input, int modulus);

link together with inverse1.obj.
Don't trust my code yet. Check if there is any wrong result produced.

eegcd-11 means Euclidean algorithm with 11 times repeated subtraction.

          eegcd-11 eegcd-10 eegcd-9 eegcd-8 eegcd-7 akruppa_C
 1048583    300      313      310     316    321      418
 2097169    315      326      324     332    333      422
 4194319    316      326      322     332    332      429
 8388617    322      331      328     337    338      437
16777259    333      343      340     350    350      457
33554467    345      355      352     363    363      475

Post the source!! If it truly is faster, the linkage problems can be fixed.
I will port it to Microsoft style ASM's. 475 to 345 is a noteworthy
improvement....

[jasonp]

Originally Posted by R.D. Silverman

Post the source!! If it truly is faster, the linkage problems can be fixed.
I will port it to Microsoft style ASM's. 475 to 345 is a noteworthy
improvement....

In the meantime, GGNFS includes a very similar modular inverse core in assembly language; go to www.sourceforge.net/projects/ggnfs and in the CVS sources look for branch_0/src/modinv1002.s

Unfortunately the code is in AT&T syntax and expects the modulus to be in a global location, so it's not plugin-compatible with the code we've been comparing.

jasonp

[akruppa]

Afaik ggnfs is distributed under the GPL, so there may be a license problem with using that code bit - unless Bob wants to put his code under the GPL as well.

Alex

[R.D. Silverman]

Originally Posted by akruppa

Afaik ggnfs is distributed under the GPL, so there may be a license problem with using that code bit - unless Bob wants to put his code under the GPL as well.

Alex

I'd be happy to put it under GPL if asked, but I see no need. I give the code
out to anyone who asks.

[xenon]

Originally Posted by R.D. Silverman

Post the source!! If it truly is faster, the linkage problems can be fixed.
I will port it to Microsoft style ASM's. 475 to 345 is a noteworthy
improvement....

The asm file is already located in the asm folder, but no comments at all. Very difficult to read. At the moment, please help verifying the speed. Actually I did nothing other than rewriting the given algorithm in assembly.

I use MASM syntax only. You should be porting from Microsoft style to gcc style.

I'd be happy to put it under GPL if asked, but I see no need. I give the code out to anyone who asks.

I believe your position is justified.

[xilman]

Originally Posted by R.D. Silverman

I'd be happy to put it under GPL if asked, but I see no need. I give the code
out to anyone who asks.

Your choice, but please take the decision having given it careful thought and with your eyes wide open.

The GPL is a kiss of death to many organizations, as it forces recipients to GPL their own material if they wish to redistribute anything containing GPL-ed components. That's why NFSNET has avoided any contributions of GPL-licensed code because it conflicts with the licensing requirements on the CWI material. NFSNET-written code is distributed under a BSD-like license.


Paul