SHARE
TWEET

FUNCTION.c

allekco May 31st, 2018 124 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <time.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <math.h>
  6. #include <stddef.h>
  7. #include "file.h"
  8.  
  9. void output (struct long_num c){
  10.     int i;
  11.     if (c.sigh == 1)
  12.             printf ("+");
  13.         else
  14.             printf ("-");
  15.     for (i = c.lengh-1 ; i >= 0; i--){
  16.         printf ("%d", c.c[i]);
  17.        
  18.     }
  19.     printf (" \n" );
  20. }
  21.  
  22. struct long_num first (int a){
  23.    
  24.     int sigh;
  25.     if (a < 0){
  26.         sigh = -1;
  27.         a = -a;
  28.     }
  29.     else
  30.         sigh = 1;
  31.  
  32.     int n, i = 0;
  33.     n = a;
  34.     struct long_num A;
  35.    
  36.     while (n != 0){
  37.         n = n/10;
  38.         i++;
  39.     }
  40.     if (( A.c = malloc ( i * sizeof ( int))) == NULL )
  41.         exit (1);
  42.     A.lengh = i;
  43.        
  44.     for (i = 0; i <= A.lengh; i++){
  45.         A.c[i] = 0;
  46.     }
  47.    
  48.     i=0;
  49.     while (a != 0){
  50.         A.c[i] = a%10;
  51.         a = a/10;
  52.         i++;
  53.     }
  54.  
  55.     A.sigh = sigh;
  56.     return A;  
  57. }
  58.  
  59. struct long_num summa_moduley (struct long_num A1, struct long_num A2){
  60.  
  61.     struct long_num sum;
  62.    
  63.     if (A1.lengh > A2.lengh){
  64.         sum.lengh = A1.lengh + 1;
  65.     }
  66.     else{
  67.         sum.lengh = A2.lengh + 1;
  68.     }
  69.     if (( sum.c = malloc ( sum.lengh * sizeof ( int ))) == NULL ){
  70.         exit (1);
  71.     }
  72.        
  73.     int i=0, count = 0, k=0;
  74.                
  75.     for (i = 0; i < sum.lengh; i++){
  76.         sum.c[i] = 0;
  77.     }
  78.    
  79.     if (A1.lengh >= A2.lengh){ 
  80.         for (i = 0; i < A2.lengh; i++){
  81.             sum.c[i] = A1.c[i] + A2.c[i] + count;
  82.             if (sum.c[i] >= 10){
  83.                 count = 1;
  84.                 sum.c[i] = sum.c[i] - 10;
  85.             }
  86.             else
  87.                 count = 0;     
  88.         }
  89.         for (i = A2.lengh; i <A1.lengh; i++){
  90.             sum.c[i] = A1.c[i] + count;
  91.             if (sum.c[i] >= 10){
  92.                 count = 1;
  93.                 sum.c[i] = sum.c[i] - 10;
  94.             }
  95.             else
  96.                 count = 0; 
  97.         }
  98.         if (count == 1)
  99.             sum.c[i]++;
  100.     }
  101.     else{
  102.         for (i = 0; i < A1.lengh; i++){
  103.            
  104.             sum.c[i] = A1.c[i] + A2.c[i] + count;
  105.             if (sum.c[i] >= 10){
  106.                 count = 1;
  107.                 sum.c[i] = sum.c[i] - 10;
  108.             }
  109.             else{
  110.                 count = 0;
  111.             }
  112.         }
  113.         for (i = A1.lengh ; i < A2.lengh; i++){
  114.             sum.c[i] = A2.c[i] + count;
  115.             if (sum.c[i] >= 10){
  116.                 count = 1;
  117.                 sum.c[i] = sum.c[i] - 10;
  118.             }
  119.             else{
  120.                 count = 0;
  121.             }  
  122.         }
  123.         if (count == 1)
  124.             sum.c[i]++;
  125.     }
  126.        
  127.     sum.sigh = 1;
  128.     return sum;
  129. }
  130.  
  131. struct long_num subtraction_moduley (struct long_num A1, struct long_num A2){
  132.  
  133.     struct long_num subtr;
  134.     int count=0, i=0;
  135.     if (A1.lengh > A2.lengh){
  136.         subtr.lengh = A1.lengh;
  137.     }
  138.     else{
  139.         subtr.lengh = A2.lengh;
  140.     }
  141.     if (( subtr.c = malloc ( subtr.lengh * sizeof ( int ))) == NULL )
  142.         exit (1);
  143.        
  144.     for (i = 0; i < subtr.lengh; i++){
  145.         subtr.c[i] = 0;
  146.     }
  147.    
  148.     int kill=11;
  149.     if (A1.lengh == A2.lengh){
  150.         i = A1.lengh-1;
  151.         kill = 0;
  152.        
  153.         while ((A1.c[i] == A2.c[i])&&(i!=-1)){
  154.             i--;
  155.         }
  156.         if (i < 0){
  157.             kill = 0;
  158.             subtr.lengh = 1;
  159.             subtr.c[0] = 0;
  160.             subtr.c[1] = 0;
  161.             subtr.sigh = 1;
  162.             return subtr;
  163.         }
  164.        
  165.         if (A1.c[i] > A2.c[i]){
  166.             kill = 1;
  167.         }
  168.         else{
  169.             kill = 2;
  170.         }
  171.        
  172.     }
  173.  
  174.     if ((A1.lengh > A2.lengh) || (kill == 1)){
  175.         count = 0;
  176.         for (i = 0; i < A2.lengh; i++){
  177.             subtr.c[i] = A1.c[i] - A2.c[i] - count;
  178.                 if (subtr.c[i] < 0){
  179.                     subtr.c[i] += 10;
  180.                     count = 1; 
  181.                 }
  182.                 else
  183.                     count = 0;
  184.         }
  185.         for (i = A2.lengh; i < A1.lengh ; i++){
  186.             subtr.c[i] = A1.c[i] - count;
  187.             if (subtr.c[i] < 0){
  188.                 subtr.c[i] += 10;
  189.                 count = 1; 
  190.             }
  191.             else
  192.                 count = 0; 
  193.         }
  194.         subtr.sigh = 1;
  195.     }
  196.     else{
  197.         for (i = 0; i < A1.lengh; i++){
  198.             subtr.c[i] = A2.c[i] - A1.c[i] - count;
  199.                 if (subtr.c[i] < 0){
  200.                     subtr.c[i] += 10;
  201.                     count = 1; 
  202.                 }
  203.                 else
  204.                     count = 0;
  205.         }
  206.         for (i = A1.lengh; i < A2.lengh ; i++){
  207.             subtr.c[i] = A2.c[i] - count;
  208.             if (subtr.c[i] < 0){
  209.                 subtr.c[i] += 10;
  210.                 count = 1; 
  211.                 }
  212.             else
  213.                 count = 0; 
  214.         }
  215.         subtr.sigh = -1;
  216.     }
  217.  
  218.     return subtr;
  219. }
  220.  
  221.  
  222. struct long_num summa (struct long_num A1, struct long_num A2){
  223.    
  224.     struct long_num sum;
  225.        
  226.     if((A1.sigh == 1) && (A2.sigh == 1)){ //1
  227.         sum = summa_moduley (A1, A2);
  228.     }
  229.      
  230.     if((A1.sigh == -1) && (A2.sigh == -1)){  //2
  231.         sum = summa_moduley (A1, A2);
  232.         sum.sigh = -sum.sigh;
  233.     }
  234.    
  235.     if((A1.sigh == 1) && (A2.sigh == -1)){ //3
  236.         sum = subtraction_moduley (A1, A2);
  237.     }
  238.    
  239.     if((A1.sigh == -1) && (A2.sigh == 1)){  //4
  240.         sum = subtraction_moduley (A2, A1);
  241. //      sum.sigh = -sum.sigh;
  242.     }
  243.    
  244. //  if (sum.c[sum.lengh]==0) sum.lengh--;
  245. //  printf ("this is sum: ");
  246. //  output (sum);
  247.     return sum;
  248. }
  249.  
  250. struct long_num subtraction (struct long_num A1, struct long_num A2){
  251.    
  252.     struct long_num subtr;
  253.        
  254.     if((A1.sigh == 1) && (A2.sigh == 1)){ //1
  255.         subtr = subtraction_moduley (A1, A2);
  256.     }
  257.      
  258.     if((A1.sigh == -1) && (A2.sigh == -1)){  //2
  259.         subtr = subtraction_moduley (A1, A2);
  260.         subtr.sigh = -subtr.sigh;
  261.     }
  262.    
  263.     if((A1.sigh == 1) && (A2.sigh == -1)){ //3
  264.         subtr = summa_moduley (A1, A2);
  265.     }
  266.    
  267.     if((A1.sigh == -1) && (A2.sigh == 1)){  //4
  268.         subtr = summa_moduley (A1, A2);
  269.         subtr.sigh = -subtr.sigh;
  270.     }
  271.    
  272.     printf ("subtraction lengh %d\n", subtr.lengh);
  273.     return subtr;
  274. }
  275.  
  276. struct long_num zeros (struct long_num B1, struct long_num B2){
  277.     int b, i;
  278.     struct long_num A1;
  279.     A1.sigh = B1.sigh;
  280.     if (B1.lengh > B2.lengh){
  281.         b = ceil(log2(B1.lengh));
  282.         printf ("b = %d", b);
  283.         if (B1.lengh == 1)
  284.             b = 1; 
  285. //      printf ("b %d  \n", b);
  286.         A1.lengh = pow (2, b);
  287.         printf ("lengh = %d", A1.lengh);
  288.         if (( A1.c= malloc ( A1.lengh * sizeof ( int ))) == NULL )
  289.             exit (1);
  290.        
  291.         for (i = 0; i < B1.lengh; i++)
  292.             A1.c[i] = B1.c[i];
  293.            
  294.         for (i = B1.lengh; i < A1.lengh; i++)
  295.             A1.c[i] = 0;   
  296.     }
  297.     else{
  298.         b = ceil(log2(B2.lengh));
  299.         if (B2.lengh == 1)
  300.             b = 1;
  301.         A1.lengh = pow (2, b);
  302. //        printf ("b %d  \n", b);
  303.         if (( A1.c = malloc ( A1.lengh * sizeof ( int ))) == NULL )
  304.             exit (1);
  305.    
  306.         for (i = 0; i < B1.lengh; i++)
  307.             A1.c[i] = B1.c[i];
  308.  
  309.         for (i = B1.lengh; i < A1.lengh; i++)
  310.             A1.c[i] = 0;   
  311.     }  
  312.     return A1;
  313. }
  314.  
  315. struct long_num kara(struct long_num B1, struct long_num B2){ // n=A1.lengh
  316.     printf ("u are in karatzuba\n");
  317.     output (B1);
  318.     printf ("lengh B1 %d\n", B1.lengh);
  319.     output (B2);
  320.     printf ("lengh B2 %d\n", B2.lengh);
  321.     int k1 = B1.lengh-1;
  322.     while (B1.c[k1]==0){
  323.         k1--;
  324.         B1.lengh --;
  325.         printf("XYI 1\n");
  326.     }
  327.     int k2 = B2.lengh-1;
  328.     while (B2.c[k2]==0){
  329.         k2--;
  330.         B2.lengh --;
  331.         printf("XYI 2\n");
  332.     }
  333.     output (B1);
  334.     printf ("lengh B1 %d\n", B1.lengh);
  335.     output (B2);
  336.     printf ("lengh B2 %d\n", B2.lengh);
  337.     printf ("u are in karatzuba\n");
  338.     output (B1);
  339.     printf ("lengh B1 %d\n", B1.lengh);
  340.     output (B2);
  341.     printf ("lengh B2 %d\n", B2.lengh);
  342.    
  343.     struct long_num Q1;
  344.     struct long_num Q2;
  345.     int j;
  346.    
  347.     if (B1.lengh > B2.lengh){
  348.     if (B1.lengh%2 == 0){
  349.         Q1.lengh = B1.lengh;
  350.         Q2.lengh = B1.lengh;
  351.     }
  352.     else{
  353.         Q1.lengh = B1.lengh+1;
  354.         Q2.lengh = B1.lengh+1;
  355.         }
  356.     if (( Q1.c = malloc ( Q1.lengh * sizeof ( int ))) == NULL )
  357.         exit (1);
  358.     if (( Q2.c = malloc ( Q2.lengh * sizeof ( int ))) == NULL )
  359.         exit (1);
  360.     if (B1.lengh%2 == 1){
  361.         Q1.c[B1.lengh] = 0;
  362.         Q2.c[B1.lengh] = 0;
  363.     }
  364.        
  365.     for(j = 0; j < B2.lengh; j++){
  366.         Q1.c[j] = B1.c[j];
  367.         Q2.c[j] = B2.c[j];
  368.     }  
  369.     for(j = B2.lengh; j < B1.lengh; j++){
  370.         Q1.c[j] = B1.c[j];
  371.         Q2.c[j] = 0;
  372.     }
  373.     }
  374.     else{
  375.         if (B2.lengh%2 == 0){
  376.             Q1.lengh = B2.lengh;
  377.             Q2.lengh = B2.lengh;
  378.         }
  379.         else{
  380.             Q1.lengh = B2.lengh+1;
  381.             Q2.lengh = B2.lengh+1;
  382.             }
  383.         if (( Q1.c = malloc ( Q1.lengh * sizeof ( int ))) == NULL )
  384.             exit (1);
  385.         if (( Q2.c = malloc ( Q2.lengh * sizeof ( int ))) == NULL )
  386.             exit (1);
  387.            
  388.         if (B2.lengh%2 == 1){
  389.             Q1.c[B2.lengh] = 0;
  390.             Q2.c[B2.lengh] = 0;
  391.         }  
  392.         for(j = 0; j < B1.lengh; j++){
  393.             Q1.c[j] = B1.c[j];
  394.             Q2.c[j] = B2.c[j];
  395.         }  
  396.         for(j = B1.lengh; j < B2.lengh; j++){
  397.             Q1.c[j] = 0;
  398.             Q2.c[j] = B2.c[j];
  399.         }
  400.     }
  401.     Q1.sigh = B1.sigh;
  402.     Q2.sigh = B2.sigh;
  403.     printf ("lengh Q1 %d\n", Q1.lengh);
  404.     output (Q1);
  405.     printf ("lengh Q2 %d\n", Q2.lengh);
  406.     output (Q2);
  407.  
  408.    
  409.     int n = Q1.lengh;
  410.     int k = n/2;
  411.     if (n<=2){
  412.         printf ("u are in n<=2\n");
  413.         int answer1 = Q1.c[0];
  414.         int answer2 = Q2.c[0];
  415.         answer1 = answer1 + Q1.c[1] * 10;
  416.         answer2 = answer2 + Q2.c[1] * 10;
  417.         struct long_num Ans;
  418.         Ans = first (answer1*answer2);
  419.         Ans.sigh = Q1.sigh * Q2.sigh;
  420.         printf ("Answer: ");
  421.         output (Ans);
  422.         return Ans;
  423.  
  424.     }
  425.     else{
  426.         printf ("good, but u are in n>2\n");
  427.         struct long_num X1;
  428.         struct long_num X2;
  429.         struct long_num Y1;
  430.         struct long_num Y2;
  431.        
  432.        
  433.         X1 = half_power (Q1);
  434.         X2 = half (Q1);
  435.         Y1 = half_power (Q2);
  436.         Y2 = half (Q2);
  437.         printf ("after do half ");
  438.        
  439.        
  440.         struct long_num p1;
  441.         struct long_num p2;
  442.         struct long_num s1;
  443.         struct long_num s2;
  444.            
  445.         printf ("again karatzuba\n");      
  446.         p1 = kara (X1, Y1);
  447.         p2 = kara (X2, Y2);
  448.        
  449.         printf ("not bad, but sum now!\n");
  450.        
  451. //      output (Y1);
  452. //      output (Y2);
  453.         s1 = summa (X1, X2);
  454.         s2 = summa (Y1, Y2);
  455. //      printf ("what we want sum:\n");
  456.  
  457. //      printf ("x1 lengh = %d\n", X1.lengh);
  458. //      printf ("x2 lengh = %d\n", X2.lengh);
  459. //      printf ("sum lengh = %d\n", s1.lengh);
  460.         printf ("value of sum: ");
  461.         output (s1);
  462.         output (s2);
  463.        
  464.         struct long_num XY1;
  465.         struct long_num XY2;
  466.         struct long_num XY3;
  467.         struct long_num XY4;
  468.         struct long_num XY5;
  469.         struct long_num XY6;   
  470.         struct long_num XY;
  471.         printf ("now is power for this lengh: ");
  472.         XY1 = powering (p1, 2*k);
  473.         output (XY1);
  474.         XY2 = kara (s1, s2);
  475.        
  476.         printf ("before subtraction we must new what we subtract: \n");
  477.         output (XY2);
  478.         output (p1);
  479.         XY3 = subtraction (XY2, p1);
  480.         printf ("this is subtraction: ");
  481.         output (XY3);
  482.         printf ("before subtraction we must new what we subtract: \n");
  483.         output (XY3);
  484.         output (p2);
  485.         XY4 = subtraction (XY3, p2);
  486.         printf ("this is subtraction: ");
  487.         output (XY4);
  488.         printf ("hi, power half lengh\n");
  489.         XY5 = powering (XY4, k);
  490.         output (XY5);
  491.         printf ("summa of: ");
  492.         output (XY1);
  493.         output (XY5);
  494.         XY6 = summa (XY1, XY5);
  495.         printf ("and result is: ");
  496.         output (XY6);
  497.        
  498.         printf ("summa of: ");
  499.         output (XY6);
  500.         output (p2);
  501.         printf ("and result is: ");
  502.         XY = summa (XY6, p2);
  503.         output (XY);
  504.  
  505.         return XY;
  506.         //xy = kara(X1,Y1) * pow(10, 2*n) + ((kara(summa(X1,X2),summa(Y1,Y2))) - kara(X1,Y1) - kara(X2,Y2)) * pow(10, n) + kara(X2,Y2);    
  507.     }      
  508. }
  509.  
  510.  
  511. struct long_num half_power (struct long_num X){
  512.         struct long_num X1;
  513.         X1.sigh = X.sigh;
  514.         X1.lengh = X.lengh/2;
  515.  
  516.         if (( X1.c = malloc ( X1.lengh * sizeof ( int ))) == NULL ){
  517.             exit (1);
  518.         }
  519.        
  520.         int i;
  521.         for (i = 0; i < X.lengh/2; i++){
  522.             X1.c[i] = X.c[i+X.lengh/2];
  523.         }
  524.         printf ("half_power: ");
  525.         output (X1);
  526.         return X1;
  527. }
  528.  
  529. struct long_num half (struct long_num X){
  530.         struct long_num X2;
  531.         X2.sigh = X.sigh;
  532.         X2.lengh = X.lengh/2;
  533.  
  534.         if (( X2.c = malloc ( X2.lengh * sizeof ( int ))) == NULL ){
  535.             exit (1);
  536.         }
  537.        
  538.         int i;
  539.         for (i = 0; i < X.lengh/2; i++){
  540.             X2.c[i] = X.c[i];
  541.         }
  542.         printf ("half: ");
  543.         output (X2);
  544.         return X2;         
  545. }
  546.  
  547.  
  548. struct long_num powering (struct long_num A, int n){
  549.     struct long_num B;
  550.     B.lengh = n + A.lengh;
  551.     if (( B.c = malloc ( B.lengh * sizeof ( int ))) == NULL )
  552.         exit (1);
  553.     B.sigh = A.sigh;
  554.     int i;
  555.     for (i = 0; i < n; i++){
  556.         B.c[i] = 0;        
  557.     }
  558.     for (i = n; i < B.lengh; i++){
  559.         B.c[i] = A.c[i-n];
  560.     }
  561.     return B;
  562. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top