c语言快速乘算法

1.基本原理

快速乘法的原理就是利用乘法分配率来将a＊b转化为多个式子相加的形式求解（注意这时使用乘法分配率的时候后面的一个乘数转化为二进制的形式计算）．举个栗子
　　20＊14　＝　20＊(1110)2 = 20＊(2^3)＊1 + 20＊(2^{2)＊1+20＊(2}1)＊１+20＊(2^0)＊0 = 160+80+40=280.

2.源码实现

#include <stdio.h>
#include <stdlib.h>

int call(int a, int b, int p)
{
    int c = 0;

    while(b)
    {
        c = (c + b % 2 * a) % p;
        a = (a << 1) % p;
        b >>= 1;
    }

    return c;
}

int main()
{
    int n = -1;
    int a, b, p;
    int i;

    scanf("%d", &n);

    if(n < 1)
    {
        return -1;
    }

    for(i=0; i<n; i++)
    {
        scanf("%d %d %d", &a, &b, &p);

        printf("%d\n", call(a, b, p));
    }

    return 0;
}

3.编译源码

$ gcc -o test test.c -std=c89

4.运行及其结果

$ ./test
4
2 2 6
3 4 10
2 2 6
3 4 10
4
2
4
2