Errors with a New Implementation of mpn/gcd.c

[Team GCD]

Hello to everyone,
 
I am new to the GMP discussion group. I, along with my partner, am working on a modified implementation of the accelerated GCD algorithm that is found within the mpn/gcd.c file. Our work is being performed to satisfy the requirements of our CS department’s software engineering class. Essentially, the task is to modify the mpn/gcd.c file to implement the changes to the algorithm proposed by Sidi Mohamed Sedjelmaci in a paper submitted to IPL. These changes remove the introduction of spurious factors into up, therefore seeking to eliminate part of the extra cleanup step required at the end of the algorithm (and potentially leading to an extended GCD algorithm based upon the accelerated algorithm).
 
We have however, ran into a few large issues with our development. Our current file works correctly when tested on two mpz_urandomb integer types. That is, our test program simply runs through a loop that generates mpz_t types with the mpz_urandomb function and then calculates their GCD. There appears to be no obvious error in our calculation methodology as we have documented correctness against results produced using the original gcd.c file.
 
However, when we change our test program to generate mpz_rrandomb numbers (the kind designed with long strings of 1s and 0s to catch corner bugs), we are unable to calculate correct results, and we typically halt with segmentation faults whenever we try reasonably large inputs or a great number of iterations. We have tried debugging on a number of different architectures including x86, IA-64, and PowerPC and have observed different behavior on all three.
 
What we can relate with some certainty is that there are instances where a pointer’s value (the vital pointers being up and vp) is getting rewritten to point to an inaccessible location (usually 0x0 or 0xffffffff). We have not observed any specific instance where this behavior could occur, and therefore we have attributed it to stack management concerns whereby the locations storing these pointers are being clobbered by other data.
 
Other behavior that we have taken note of is that the problem tends to be alleviated if we add extra junk to the stack. That is, when we inserted a number of a gmp_printf() statements for debugging purposes, the program would run through a few more iterations before crashing, leading us to believe that a stack overlapping issue was present and adding extra information to the stack simply prolonged the inevitable side-effect.
 
We are relatively new to the GMP library (after only having been introduced to it and essentially the GNU/Linux environment late this semester). We are also less familiar with C than with Java or other O-O style languages, but this project has been a great deal of fun and we are simply hoping to iron out these bugs.
 
Once we can resolve the issues, our main intent is to test this implementation against the original implementation that is currently provided in the mpn/gcd.c file. Our hypothesis and some preliminary data suggest that we could discover a level of speedup around the 900-1000 bit range. Needless to say, we are very anxious to test this new implementation and to see what potential benefits it could provide (particularly relating to an extended GCD algorithm built from this accelerated base).
 
We would hope that if anyone has any interest at all in helping us debug or test this code, that they would contact us at teamgcd at hotmail.com. Also, our project’s website is located at http://raider.muc.edu/~prodonjs/sceblog/index.html and it can provide some more background information on the new algorithm as well as our current status.
 
If anyone is more interested, please contact us and we can distribute our current source version. As I’ve said before, we are two students just getting our feet wet with a UNIX-style environment and low-level mathematical programming. We are enjoying ourselves greatly, but are reaching the limits of our understanding of the GMP memory management system. We are hoping for any response to our problem. Thank you for your consideration.
 
Jason Prodonovich
Mount Union College
_________________________________________________________________
It’s tax season, make sure to follow these few simple tips 
http://articles.moneycentral.msn.com/Taxes/PreparationTips/PreparationTips.aspx?icid=WLMartagline
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://gmplib.org/list-archives/gmp-discuss/attachments/20070321/a8045993/attachment.html