一道作业题，有关低级处理，效率，Karatsuba算法
#include <stdio.h>#include <stdlib.h>
#include <time.h>
#define SWAP(a,b) { a ^= b; b ^= a; a ^= b; }
unsigned long int karatsuba(unsigned long int a, unsigned long int b);
int main () {
unsigned long int a, b;
srand(time(NULL));
#ifndef TEST
a=rand(); b=rand();
printf("%ld*%ld=%ld\n",a,b,karatsuba(a,b));
#endif
#ifdef TEST
for(int i=0; i< 1000000; i++) {
a=rand(); b=rand();
if(karatsuba(a,b)!=a*b) {
fprintf(stderr,"Error: a=%ld, b=%ld\n",a,b);
exit(-1);
}
}
#endif
}
unsigned long int karatsuba(unsigned long int a, unsigned long int b) {
int i, n, N;
unsigned long int x0, y0;
unsigned long int z0, z1, z2;
if(a<b) SWAP(a,b);
if(b==0) return 0;
for(n=-1, i = 1; i <= b; i<<=1, n++);/* not optimal */
for(N=n; i <= a; i<<=1, N++);
y0=b&((1<<n)-1);
x0=a&((1<<N)-1);
z2=1<<(N-n);
z1=karatsuba(z2,y0)+x0;
z0=karatsuba(x0,y0);
return (z2<<(2*n))+(z1<<n)+z0;
} 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 */ 的地方？
页:
[1]