Thread: Peasants' Algorithm for multiplication

Originally Posted by A.B.D

Q.7 Consider the Peasants' Algorithm for multiplication of two positive integers. It
works in the following manner:
• Write the two numbers in two columns. Keep updating according to the
following procedure until the number in the first (i.e., left) column becomes 1.
• Halve the number in the first column (integer division), double the number in
the second column.
• In the end, sum up all the numbers in the second column, for which, the
corresponding number in the first column is odd.
Example of multiplication using Peasants’ algorithm: 13 x 8:
13 8 ←
6 16
3 32 ←
1 64 ←
Answer: 64 + 32 + 8 = 104
Write a function to calculate multiplication using the Peasants’
algorithm.

Code:

#include<stdio.h>
int main()
{
    int n1,n2,c1,c2,sum=0;
    printf("Enter two numbers: ");
    scanf("%d%d",&n1,&n2);
    c1=n1;c2=n2;
    while(c1>=1)
    {
        if(c1%2==1)
            sum+=c2;
        c1/=2;c2*=2;
    }
    printf("The product of %d and %d is %d",n1,n2,sum);
}

Do go through this, And thank you for constructive criticism.

Formatting's not great, but it does look pretty kosher. You could however do things a bit more efficiently:

Code:

#include<stdio.h>
int main()
{
    int n1,n2,c1,c2,sum=0;
    printf("Enter two numbers: ");
    scanf("%d%d",&n1,&n2);
    c1=n1;c2=n2;
    while(c1>=1)
    {
        if(c1&1)
            sum+=c2;
        c1>>=1;c2<<=1;
    }
    printf("The product of %d and %d is %d\n",n1,n2,sum);
}

Lmao:d:d

Originally Posted by Alogon

This peasant's algorithm is interesting. If I must repeatedly multiply numbers by a single known multiplier such as 40, I am at least tempted to use addition and shifting rather than actual multiplication in hopes of efficiency. Doing so involves no ifs, ands (or buts..). This algorithm is a kind of generalization of the same idea, but it comes at the cost of comparison and branching, which must would make it slower in practice than a CPU's multiplication instruction. Could it be that the peasant's algorithm is how the multiplication instruction works in the hardware itself?

I have no idea, but I'm guessing most likely not. Even though the peasant's algorithm is basically equivalent to long multiplication, the latter is easier to implement. Older CPU's used that method almost exclusively. Modern chips tend to use more advanced approaches, and hence overall performance has improved dramatically.

Galahad's added only one code. The other code is part of his signature.

Originally Posted by A.B.D

Thank you Brother.
But I didn't get your Second code.
Can u explain it.

It's just a simple demonstration of the connection between the "coprimality" of all the integers and the mathematical constant "pi" (ie: 3.1415926[...]). It works even better if you're sampling from a truly random source. (Only reason I opted for rand() was to keep things as platform-neutral as possible.)