一道作业题，有关低级处理，效率，Karatsuba算法

techmagician

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <time.h>
   
4. #define SWAP(a,b) { a ^= b; b ^= a; a ^= b; }
   
5. 
   
6. unsigned long int karatsuba(unsigned long int a, unsigned long int b);
   
7. int main () {
   
8.     unsigned long int a, b;
   
9.     srand(time(NULL));
   
10.    
    
11.    
    
12. #ifndef TEST
    
13.     a=rand(); b=rand();
    
14.     printf("%ld*%ld=%ld\n",a,b,karatsuba(a,b));
    
15. #endif
    
16.    
    
17. #ifdef TEST
    
18.     for(int i=0; i< 1000000; i++) {
    
19.         a=rand(); b=rand();
    
20.         if(karatsuba(a,b)!=a*b) {
    
21.             fprintf(stderr,"Error: a=%ld, b=%ld\n",a,b);
    
22.             exit(-1);
    
23.         }
    
24.     }
    
25.    
    
26. #endif
    
27. }
    
28. 
    
29. unsigned long int karatsuba(unsigned long int a, unsigned long int b) {
    
30.     int i, n, N;
    
31.     unsigned long int x0, y0;
    
32.     unsigned long int z0, z1, z2;
    
33.     if(a<b) SWAP(a,b);
    
34.     if(b==0) return 0;
    
35.     for(n=-1, i = 1; i <= b; i<<=1, n++);  /* not optimal */
    
36.     for(N=n; i <= a; i<<=1, N++);
    
37.     y0=b&((1<<n)-1);
    
38.     x0=a&((1<<N)-1);
    
39.     z2=1<<(N-n);
    
40.     z1=karatsuba(z2,y0)+x0;
    
41.     z0=karatsuba(x0,y0);
    
42.     return (z2<<(2*n))+(z1<<n)+z0;
    
43. }

复制代码

                                                                                                                                        Explainwhat specific adjustments were made to the algorithm inorder to improve the efficiency.



                                                                                                Write an efficient function to replace the for loops marked as “notoptimal”. Hint: you can use some assembler instructions (keyword asm), some build-incompiler functions (dependent on your compiler), or the operators &, |, << and >>
                               
                       
               
                               
                       
               


题目大致意思是说这段代码用karatsuba算法在算两个数乘积，但是用了low level的处理，让解释一下它的高效在哪.
谁能解释一下那个karatsuba函数里的代码是在干些什么啊？顺便，如何改进/* not optimal */ 的地方？