Calculate square of a number without multiplication

Question

I wrote these two methods to calculate the square of a number:

static int sqr(int val)
{
    int valSqr = 0;

    for (int i = 0; i < val; i++)
        valSqr += val;

    return valSqr;
}

static int sqr(int val)
{
    int valSqr = 0;

    for (int i = 0, j = 1; i < val; i++, j += 2)
        valSqr += j;

    return valSqr;
}

The first one simply adds the given number to a value until it has been added number times. The second one uses the 1+3+5... sequence. I tried to profile this on Visual Studio, but the report was taking a really long time (over two hours) to be generated after the data collection was done. I am particularly interested in which of these methods will run faster, and which is less resource intensive (would the second one be slightly more resource intensive because there are more variables?).

Answer 1

A more efficient way to do this is to keep doubling the product while you can....

So, for example, \$5^2\$ is:

$$\begin{eqnarray*} 5 +& 5 &\longrightarrow 10 \\ 10 +& 10 &\longrightarrow 20 \end{eqnarray*} $$

then add the last 5 to get 25.

This can be done efficiently by using bit shifting:

public static int sqr (int val)
{
    int mask = 1;
    int factorsum = val;
    int sum = 0;
    while (val >= mask)
    {
        if ((val & mask) == mask)
        {
            sum += factorsum;
        }
        factorsum += factorsum;
        mask += mask;
    }
    return sum;
}

This is a \$O(\log(n))\$ solution to the problem. See it in ideone too

Answer 2

Well you could always start with val so you have to make one less addition:

static int Square(int val)
{
    int valSqr = val;

    for (int i = 0; i < val-1; i++){
        valSqr += val;
    }
    return valSqr;
}

Also, please remind to use always braces, and respect the conventions of the language. I renamed the method Square. Also please remind that this algorithm only works for positive numbers, if you want it to work for negative numbers also you could do something like:

static int Square(int val)
{
    int aux = Math.Abs(val);
    int valSqr = aux ;

    for (int i = 0; i < aux -1; i++){
        valSqr += aux ;
    }
    return valSqr;
}

Answer 3

One comment I can make is that the first method is easily changed to support the multiplication of two separate values, while the second isn't:

static int Multiple(int val1, int val2)
{
    int newVal = 0;

    if (val1 >= 0 && val2 >= 0 || val1 < 0 && val2 < 0)
    {
        val1 = Math.Abs(val1);
        val2 = Math.Abs(val2);

        for (int i = 0; i < val2; i++)
        {
            newVal += val1;
        }
    }
    else
    {
        if (val1 < val2)
        {
            int tmp = val1;
            val1 = val2;
            val2 = tmp;
        }

        for (int i = val2; i < 0; i++)
        {
            newVal -= val1;
        }
    }

    return newVal;
}

The first relies on a special algorithm to calculate squares.

Answer 4

Neither is the most efficient. The square of any number \$x\$ is

\$(x-1)**2 +(x-1) + x\$

Or in English instead of math, the square of any number is equal to the number less than it squared + the number less than it + the number itself. eg: 5 squared = 4 squared (16) + 4 (subtotal 20) + 5 (total = 25). This is true for all positive whole numbers.

So, for example, you're squaring a million: you'd have to add a million to itself a million times, but using as many loops, my routine was finding the square of 1, 2, 3...1,000,000. So the processor only has to handle a number as large as a million once, instead of a million times.

When I was in Intro to Computer Science in 1978 I wrote a Basic routine like this (where X is the number to be squared, L is loop counter and S is the resulting square, all defined as integers):

DEF X, L, S as Int

S=0

for L = 1 to X

     S=S+L-1+L

Next

? "The square of",X," equals",S

Back in the fall of 1977 when this was written, the Mainframe at my college had a 4-bit processor (which could operate on numbers between 0 and 15 without storing and carrying). I had the program grab the time, square the numbers 1 to 100 using the computer's intrinsic square function and grab the time again, subtracting the starting time from the ending time to see how long the computer took to square the 1st 100 numbers in machine language. I grabbed times on either side of the routine running my formula on the same 100 numbers. It was .02 seconds faster to run my higher language routine than the computer's built in square function.

The school, auditing computer use by the various classes, noticed my program and called me in to meet the fellow with the doctorate running the department. They were amazed that a 1st year programmer was proving mathematical theory instead of fighting his way through the idea of programming. Researched it and published a paper at the ensuing mathematical conference. Within a year, it (and its associated programs for squaring negative, fractional and mixed numbers were adopted in machine language as ROM for the square function by 3 of the 4 largest mainframe manufacturers. The year in review for technology's computer expert said it would save heavy computer users (colleges, military, engineering firms) $3.56B in CPU time per year. hope that helps.

Answer 5

• you really should use braces {} for single statement body of a for loop.
• you shouldn't shorten variables and parameter names
• doing multiple initializations and incrementing inside a loop will remove readability.

Answer 6

Naming

I'm not a C# programmer but personally I'm not a fan of sqr or valSqr names. I would use something less obfuscating like square and valSquare.

Answer 7

To answer your specific question: the second version should be slower. Both of them perform the same number of loops. However, in the second version, each loop has more addition operations, as it also has to increment j.

Answer 8

With this CPU that supports addition and subtraction, but not bit-shifting, I would assume that there are only a handful of registers available on the chip, which could yield even simple algorithms to be too complicated. I'm not sure C# would be the optimal language for programming this chip. It would also help to know the rest of the constraints that your embedded system has.

Assuming only 8 bit integers (a chip with no bit shifting would not support 64 bit integers!), there are only 16 squares that need to be calculated, the rest overflow. These could be easily stored as a 16 byte array in ROM - much faster and at a comparable size to a callable function.

As you have indicated performance is an issue, and in the chance that you need to support 32 bit integers, using the same method an array of \$2^{20}\$ bytes - 1MB of ROM would support every 32 bit square without overflow. This yields optimal performance while taking all the load off your minimalist CPU.