Abort Trap 1

[gijunior]

Hi, I have recreated Fermat's alg for factorising numbers using GMP's bignum. However when I try to factor extremely large numbers e.g.3049818439605086085304554688619895660771188041 327
I get an 'abort trap'

Can anyone tell me - What is an abort trap?

I have no problem with numbers up until then.

My code is below.


#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include "gmp.h"

clock_t start, end;
double cpuTime;

void fermat(mpf_t n){

mpf_t a, b, bsq, p, q, result, asq, sqrtbsq, ceil_sqrtbsq, a_sub_sqrtbsq, a_add_sqrtbsq, sqrtbsq_sub_ceilsqrtbsq;
int compValue;
mpf_t sqrtn;
mpf_init(a);
mpf_init(asq);
mpf_init(b);
mpf_init(bsq);
mpf_init(p);
mpf_init(q);
mpf_init(result);
mpf_init(sqrtn);
mpf_init(a_sub_sqrtbsq);
mpf_init(a_add_sqrtbsq);
mpf_init(sqrtbsq);
mpf_init(ceil_sqrtbsq);
mpf_init(sqrtbsq_sub_ceilsqrtbsq);

start = clock(); /*starts timing CPU Time*/

/*based on the belief that (a^2 - b^2) = n*/
mpf_sqrt(sqrtn, n); /*calculates root n*/
mpf_ceil(a, sqrtn); /*a = ceil(sqrt)*/


mpf_mul(asq, a, a); /*sets asq to a*a*/
mpf_sub(bsq, asq, n); /*sets bsq to asq-n. These 2 lines equivalent of : bsq = (a*a) - n;*/


mpf_sqrt(sqrtbsq, bsq);
mpf_ceil(ceil_sqrtbsq, sqrtbsq);
mpf_sub(sqrtbsq_sub_ceilsqrtbsq, sqrtbsq, ceil_sqrtbsq); /*sets sqrtbsq_sub_ceilsqrtbsq to sqrt(bsq) - ceil(sqrt(bsq))*/
//compValue = mpf_cmp_ui(sqrtbsq_sub_ceilsqrtbsq, 0); /*compares sqrtbsq_sub_ceilsqrtbsq and 0 for while loop*/

while(compValue!= 0){
compValue = mpf_cmp_ui(sqrtbsq_sub_ceilsqrtbsq, 0); /*compares sqrtbsq_sub_ceilsqrtbsq and 0 for while loop*/

/*while b squared isnt a square number we increment a until it is*/

mpf_add_ui(a, a, 1); /*a++*/

mpf_mul(asq, a, a);
mpf_sub(bsq, asq, n); /*//bsq = (a*a) - n;*/

mpf_sqrt(sqrtbsq, bsq);
mpf_ceil(ceil_sqrtbsq, sqrtbsq);
mpf_sub(sqrtbsq_sub_ceilsqrtbsq, sqrtbsq, ceil_sqrtbsq);
//compValue = mpf_cmp_ui(sqrtbsq_sub_ceilsqrtbsq, 0);


}
/*once bsq becomes a squared number, we return a - root(bsq) and a+root(bsq)*/




/*p = a - sqrt(bsq);*/
mpf_sub(p, a, sqrtbsq);
/*q = a + sqrt(bsq);*/
mpf_add(q, a, sqrtbsq);

end = clock(); /*Stops timing CPU Time*/

cpuTime= (end-start)/ (CLOCKS_PER_SEC);

//mpf_set(q, a_add_sqrtbsq);


printf("Efficiency - CPU TIME\n");
printf("%lf\n", cpuTime);

gmp_printf("%Ff %Ff\n", p, q);

/*result = p * q; */
mpf_mul(result, p, q);

}




int main(void){

mpf_t n;
mpf_init;
gmp_scanf("%Ff", n);
fermat;


}

Cheers. Very grateful!

 

[Salem]

Please use the [tt][ignore]

[/ignore][/tt] tags when posting code.

> Can anyone tell me - What is an abort trap?
Your program dying in an unexpected way.


--

 

[gijunior]

ok cheers. Yeh ddint see those tags. So it is not expecting it to die but it is. Thats great cheers.
So its not because even with GMP my platform cant cope with the size of number?

 

[Salem]

How about it being a mistake in your code?

(gdb) run
3049818439605086085304554688619895660771188041327

Program received signal SIGFPE, Arithmetic exception.
0x006f9867 in __gmp_exception (error_bit=4) at ../errno.c:40
	in ../errno.c
(gdb) bt
#0  0x006f9867 in __gmp_exception (error_bit=4) at ../errno.c:40
#1  0x006f9894 in __gmp_sqrt_of_negative () at ../errno.c:51
#2  0x006fbc99 in __gmpf_sqrt (r=0xbfbf519c, u=Variable "u" is not available.
) at ../../mpf/sqrt.c:39
#3  0x0804880a in fermat (n=0xbfbf5254) at foo.c:42
#4  0x0804897b in main () at foo.c:102
(gdb)

According to this, it seems to be trying to compute the square root of a negative number.


> while(compValue!= 0)
You don't initialise this value, so it could just be skippin the whole loop.

--

 

[gijunior]

totally correct, sorted it now. cheers guys.

After making the changes i have noticed something strange though. This program is designed to take in a composite int with 2 prime factors and output those factors. I create the comp int from the 2 factors first then factorise as im only interested in the time it takes.

this number
340282366920940618817845667806611141353
from these factors
18446744073709610033
18446744073709610041

will factor in 0 seconds

340282366920940618817845667806611141353
Efficiency - CPU TIME
0.000000
18446744067635609037.766938 18446744079783611038.233062

but this number
340282366920940989043999227158585280143
from
18446744073709620143 *18446744073709620001
does not seem to. i.e. it takes a long time to do anything, by which point i terminate because it shouldnt be taking that long when the 2 sets of factors are only 10000 apart.

This has royally stumped me. Can anyone see why this is happening?
I am not familiar with programs (full stop!)that push hardware to cetain limits.


Drew

 

[Diancecht]

I guess that has more to do with the algorithm itself and the way you coded it that with a programming issue.

Cheers,
Dian

 

[gijunior]

Hi,

Sorry to appear rude, but can you explain why that isn't a programming issue?

Cheers

Drew

 

[Diancecht]

No problem. It doesn't appear rude to me.

What I'm trying to say is that, from a programmer's point of view, the error you described does not neccesarily need to be an error.

I'm not an expert on Fermat's algorithms and I don't know if that's the correct result and the factorization depends on the distance between the number's prime factor rather than the number itself.

So it's difficult to help you since the problems seems to be related to the algorithm implementation details, not to a "regular" programming issue.

Cheers,
Dian