Advertisement
AliAbdulKareem

recursive_mul

Jan 27th, 2022
989
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2.  
  3. typedef struct halves
  4. {
  5.     int first_half;
  6.     int second_half;
  7.     unsigned int first_half_pow;
  8.  
  9. } halves;
  10.  
  11. unsigned int num_power_calculate(int x)
  12. {
  13.     unsigned int i = 0;
  14.     while( x != 0)
  15.     {
  16.         x /= 10;
  17.         ++i;
  18.     }
  19.     return i;
  20. }
  21.  
  22. halves halves_compute(int n)
  23. {
  24.     unsigned int n_digit_count = num_power_calculate(n);
  25.  
  26.     halves h = {1,1,0,0};
  27.  
  28.     for (unsigned int i = 0; i < n_digit_count/2; ++i)
  29.     {
  30.         h.first_half *= 10;
  31.     }
  32.  
  33.     h.second_half = n / h.first_half;
  34.     h.first_half  = n % h.first_half;
  35.  
  36.     h.first_half_pow = n_digit_count / 2;
  37.  
  38.     return h;
  39.  
  40. }
  41.  
  42. unsigned int ten_power(unsigned int power)
  43. {
  44.     unsigned val = 1;
  45.     while ((power > 0))
  46.     {
  47.         val *= 10;
  48.         --power;
  49.     }
  50.     return val;
  51. }
  52.  
  53. int katsubara(int x, int y)
  54. {
  55.     // decompose x into a , b (if x is 1234 -> a = 12 & b = 34) and same for y
  56.     if(x < 10 || y < 10) return x * y;
  57.  
  58.     halves h1 = halves_compute(x);
  59.     halves h2 = halves_compute(y);
  60.  
  61.  
  62.     int ac = katsubara(h1.second_half, h2.second_half);
  63.     int bd = katsubara(h1.first_half, h2.first_half);
  64.  
  65.  
  66.     int ad = katsubara(h1.second_half, h2.first_half);
  67.     int bc = katsubara(h1.first_half, h2.second_half);
  68.  
  69.     unsigned int ac_power = ten_power(h1.first_half_pow + h2.first_half_pow);
  70.    
  71.     unsigned int ad_power = ten_power(h1.first_half_pow);
  72.     unsigned int bc_power = ten_power(h2.first_half_pow);
  73.  
  74.     return  ((int)ac_power * ac) + ((int)ad_power * ad)  +((int)bc_power * bc) +  bd;
  75.    
  76. }
  77.  
  78. int main()
  79. {
  80.     int x = katsubara(11,1111);
  81.     printf("%d\n", x);
  82. }
  83.  
  84.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement