API tools faq
paste
Advertisement
allekco

FUNCTION.c

allekco
May 31st, 2018
163
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 11.01 KB | None | 0 0
raw download clone embed print report
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!