# 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.