Results 1 to 6 of 6

Math Help - factorization of number

  1. #1
    Newbie
    Joined
    Nov 2010
    Posts
    11

    factorization of number

    I have written a C code program for factorization of a given number into two divisors, when the two divisors are having approximately the same number of digits . It cannot check for prime numbers.

    With my code limit I can check it only upto 14 digits using long long int. It is working perfectly upto these 14 digits (condition is the two divisors must have app the same no.of.digits). Bigger than 14 digits it is yielding wrong answers.

    because it is a math forum, I like to post the code here. So that someone can check its efficiency for large numbers.

    If anyone's idea is to use GMP libray, I have already installed gmp using msys, and had written a C code program using gmp. The problem I faced is, when I compiled the program , it compiled perfectly. But when I selected to Run the code, It says "Project is stopped working". The problem is in input and output code lines i.e., I used printf and scanf functions to get o/p and i/p.
    To avoid this problem I did not find any best tutorial on GMP. And I did not understand what he is saying about the o/p and i/p functions, in the Documentation of GMP-5.0.1.
    If you accept to post the code using gmp , I will post that also.

    Thankful for the forum mentors and moderators and users , and for any replies given.

    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<math.h>
    #include<process.h>
    #include <time.h>
    main()
    {
    time_t result;
    long long int a,b=0,x=0,y=0,z=0,c,c1,d,e,f,p,n1n2,l=0,p4,p7,p8,p9,disc;
    double t=2,n11,m[100],p6,p5=1,p11=1,x1,x2,p1,p2;
    double sqtr();
    
    FILE *filea1b_3 = fopen("filea1b_3.txt" , "w");
    printf("Enter the value of P : ");
    scanf("%I64u",&p);
    printf("So , Given P = %I64u . \n\n\n\n",p);
    fprintf(filea1b_3, "So , Given P = %I64u . \n",p);
    p1=sqrt(p);
    p4=p1;
    p6=p1-p4;
    if(p6>0)
    {
    for(a=2;(p5&&p11)>0;a++)
    {
    x++;
    f=a*a;
    for(b=1;b<f;b++)
    {
    if((p-b)%a==0)
    {
    y++;
    n11=(((p+b)-(sqrt(4*p*b)))/(a*a));
    p4=n11;
    p5=n11-p4;
    p6=n11-p5;
    p7=p6;
    for(c=1;c<=(b/2);c++)
    {
    if(b%c==0)
    {
    z++;
    c1=(b/c);
    
    disc=((b+(a*a*p7)-p)*(b+(a*a*p7)-p))-(4*a*c*a*p7*(b/c));/*to find discriminant*/
    if(disc>0)/*distinct roots*/
    {
    x1=(p-b-(a*a*p7)+sqrt(disc))/(2*a*(b/c));
    x2=(p-b-(a*a*p7)-sqrt(disc))/(2*a*(b/c));
    }
    if(disc==0)/*Equal roots*/
    {
    x1=x2=(p-b-(a*a*p7))/(2*a*c);
    }
    if(disc<0)
    {
    x1=(p-b-(a*a*p7))/(2*a*c);/*complex roots*/
    x2=sqrt(fabs(disc))/(2*a*c);
    }
    p4=x1;
    p5=x1-p4;
    p6=x1-p5;
    p8=p6;
    p4=x2;
    p11=x2-p4;
    p6=x2-p11;
    p9=p6;
    if((p5==0)||(p11==0))
    {
    n1n2=x1*x2;
    d=x+y+z;
    e=(p-b)/a;
    printf("\n\nNo.of.loops = %I64u\n",d);
    printf("a = %I64u, b= %I64u, N = %I64u, N1 = %f, N2 = %f, N1N2 = %I64u",a,b,e,x1,x2,n1n2);
    printf("\n\nb1 = %d and b2 = %d (or) b1 = %d and b2 = %d\n\n",c,c1,c1,c); 
    fprintf(filea1b_3, "\n\nNo.of.loops = %I64u\n",d);
    fprintf(filea1b_3, "a = %I64u, b= %I64u, N = %I64u, N1 = %f, N2 = %f, N1N2 = %I64u",a,b,e,x1,x2,n1n2);
    fprintf(filea1b_3, "\n\nb1 = %d and b2 = %d (or) b1 = %d and b2 = %d\n\n",c,c1,c1,c); 
    getch();
    exit(0);
    }
    }
    }
    if((p5==0)||(p11==0))
    {
    exit(0);
    }
    b=b+a-1;
    }
    }
    }
    }
    else 
    {
    printf(" Given number is a perfect square");
    printf(" P = %f^2 ",p1);
    fprintf(filea1b_3, " Given number is a perfect square");
    fprintf(filea1b_3, " P = %f^2 ",p1);
    }
    getch();
    }


    As I said the two divisors should be closer to each other in terms of no.of.digits. This will give one factor and the other will be given number divided by the above obtained factor. It will not work on prime numbers.

    here factor is (aN1+b1) if we got N1 as an integer . or (aN2+b1) if we got N2 as an integer.
    Here b1 = anyone of the b1 values we got in the answer.

    Any replies given will be helpful to me . thanks.
    Last edited by ssnmanikanta; November 10th 2010 at 01:50 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ssnmanikanta View Post
    I have written a C code program for factorization of a given number into two divisors, when the two divisors are having approximately the same number of digits . It cannot check for prime numbers.

    With my code limit I can check it only upto 14 digits using long long int. It is working perfectly upto these 14 digits (condition is the two divisors must have app the same no.of.digits). Bigger than 14 digits it is yielding wrong answers.

    because it is a math forum, I like to post the code here. So that someone can check its efficiency for large numbers.

    If anyone's idea is to use GMP libray, I have already installed gmp using msys, and had written a C code program using gmp. The problem I faced is, when I compiled the program , it compiled perfectly. But when I selected to Run the code, It says "Project is stopped working". The problem is in input and output code lines i.e., I used printf and scanf functions to get o/p and i/p.
    To avoid this problem I did not find any best tutorial on GMP. And I did not understand what he is saying about the o/p and i/p functions, in the Documentation of GMP-5.0.1.
    If you accept to post the code using gmp , I will post that also.

    Thankful for the forum mentors and moderators and users , and for any replies given.

    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<math.h>
    #include<process.h>
    #include <time.h>
    main()
    {
    time_t result;
    long long int a,b=0,x=0,y=0,z=0,c,c1,d,e,f,p,n1n2,l=0,p4,p7,p8,p9,disc;
    double t=2,n11,m[100],p6,p5=1,p11=1,x1,x2,p1,p2;
    double sqtr();
    
    FILE *filea1b_3 = fopen("filea1b_3.txt" , "w");
    printf("Enter the value of P : ");
    scanf("%I64u",&p);
    printf("So , Given P = %I64u . \n\n\n\n",p);
    fprintf(filea1b_3, "So , Given P = %I64u . \n",p);
    p1=sqrt(p);
    p4=p1;
    p6=p1-p4;
    if(p6>0)
    {
    for(a=2;(p5&&p11)>0;a++)
    {
    x++;
    f=a*a;
    for(b=1;b<f;b++)
    {
    if((p-b)%a==0)
    {
    y++;
    n11=(((p+b)-(sqrt(4*p*b)))/(a*a));
    p4=n11;
    p5=n11-p4;
    p6=n11-p5;
    p7=p6;
    for(c=1;c<=(b/2);c++)
    {
    if(b%c==0)
    {
    z++;
    c1=(b/c);
    
    disc=((b+(a*a*p7)-p)*(b+(a*a*p7)-p))-(4*a*c*a*p7*(b/c));/*to find discriminant*/
    if(disc>0)/*distinct roots*/
    {
    x1=(p-b-(a*a*p7)+sqrt(disc))/(2*a*(b/c));
    x2=(p-b-(a*a*p7)-sqrt(disc))/(2*a*(b/c));
    }
    if(disc==0)/*Equal roots*/
    {
    x1=x2=(p-b-(a*a*p7))/(2*a*c);
    }
    if(disc<0)
    {
    x1=(p-b-(a*a*p7))/(2*a*c);/*complex roots*/
    x2=sqrt(fabs(disc))/(2*a*c);
    }
    p4=x1;
    p5=x1-p4;
    p6=x1-p5;
    p8=p6;
    p4=x2;
    p11=x2-p4;
    p6=x2-p11;
    p9=p6;
    if((p5==0)||(p11==0))
    {
    n1n2=x1*x2;
    d=x+y+z;
    e=(p-b)/a;
    printf("\n\nNo.of.loops = %I64u\n",d);
    printf("a = %I64u, b= %I64u, N = %I64u, N1 = %f, N2 = %f, N1N2 = %I64u",a,b,e,x1,x2,n1n2);
    printf("\n\nb1 = %d and b2 = %d (or) b1 = %d and b2 = %d\n\n",c,c1,c1,c); 
    fprintf(filea1b_3, "\n\nNo.of.loops = %I64u\n",d);
    fprintf(filea1b_3, "a = %I64u, b= %I64u, N = %I64u, N1 = %f, N2 = %f, N1N2 = %I64u",a,b,e,x1,x2,n1n2);
    fprintf(filea1b_3, "\n\nb1 = %d and b2 = %d (or) b1 = %d and b2 = %d\n\n",c,c1,c1,c); 
    getch();
    exit(0);
    }
    }
    }
    if((p5==0)||(p11==0))
    {
    exit(0);
    }
    b=b+a-1;
    }
    }
    }
    }
    else 
    {
    printf(" Given number is a perfect square");
    printf(" P = %f^2 ",p1);
    fprintf(filea1b_3, " Given number is a perfect square");
    fprintf(filea1b_3, " P = %f^2 ",p1);
    }
    getch();
    }


    As I said the two divisors should be closer to each other in terms of no.of.digits. This will give one factor and the other will be given number divided by the above obtained factor. It will not work on prime numbers.

    here factor is (aN1+b1) if we got N1 as an integer . or (aN2+b1) if we got N2 as an integer.
    Here b1 = anyone of the b1 values we got in the answer.

    Any replies given will be helpful to me . thanks.
    Try commenting your code, sort out the indentation and post the algorithm you think this implements.

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Jskid's Avatar
    Joined
    Jul 2010
    Posts
    160
    The number may be too large for long long int. long long int is a non-standard data type and it is not guaranteed to work on all compilers. What does your computer give you with this code?
    Code:
    int size = sizeof (long long int);
    printf ("%i", size);
    If it gives you 8 you should be fine up to 15 digit numbers according to here.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Jskid View Post
    The number may be too large for long long int. long long int is a non-standard data type and it is not guaranteed to work on all compilers. What does your computer give you with this code?
    Code:
    int size = sizeof (long long int);
    printf ("%i", size);
    If it gives you 8 you should be fine up to 15 digit numbers according to here.
    That link does not mention a "long long int" nor any 8 byte integer types. What you seem to be referring to is the precision of a double precision float for your 15 decimal digits.

    You can use double precision floats to hold integer values but you have effectively 52 or 53 bits (you can do the same trick with wider float types, but these are not exactly standardised yet).

    Of course this could always be recoded in a system that supports arbitrary precision arithmetic, such as a CAS, or you could use the extended/arbitrary precision libraries available for C++/Java.

    CB
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member Jskid's Avatar
    Joined
    Jul 2010
    Posts
    160
    When I run the code on my computer I get 8 bytes. The website says that should be about a 15 digit number in binary notation. However on the OP's computer a long long int may not be 8 bytes.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Jskid View Post
    When I run the code on my computer I get 8 bytes. The website says that should be about a 15 digit number in binary notation. However on the OP's computer a long long int may not be 8 bytes.
    The longest signed integer representable in 64 bits is 2^{64}-1 which will give ~18-19 decimal digits (but there is no such standardised type IIRC), the 15 you mention corresponds to the 52 bit mantissa of a double (float)

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Factorization of x in Z_4[x]
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 3rd 2011, 11:21 PM
  2. Irreducible factorization in number ring.
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 24th 2010, 02:43 PM
  3. [Factorization] Factorization of polynomials
    Posted in the Algebra Forum
    Replies: 9
    Last Post: April 9th 2010, 01:15 AM
  4. Replies: 2
    Last Post: March 4th 2010, 02:49 AM
  5. Factorization
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 21st 2008, 02:45 PM

Search Tags


/mathhelpforum @mathhelpforum