0
\$\begingroup\$

My problem is following: I want to Find Square root of a number (which is the square of integer) only with addition or subtraction (or together). I wrote the algorithm which works, but I am really interested in what will be better solution to solve this problem.

static void FindSquareRoot(int S)
{
    int i = 1;

    for (; i <= S; i++)
    {
        int k = S;
        int j = i;

        while (j>0)
        {
            k = k - i;
            j--;
        }

        if (k == 0)
        {
            Console.WriteLine("Square root of {0} is {1}", S, i);
            break;
        }
        else if (k < 0)
        {
            Console.WriteLine("Not found");
            break;
        }
    }
}

The basic idea of this algorithm is to choose one number(i) and subtract it from S (i) times. if the result will be 0, then it means that this(i) is the number I was looking for..

\$\endgroup\$
0

2 Answers 2

1
\$\begingroup\$

This is a type of question I usually avoid because I see little educational value in it. If I were teaching beginners C#, I wouldn't devise such an awkward example where you can't smartly use the framework's Math.Sqrt or even operations such as multiplication or division.

Here at CR, we place a premium on readable code. Other than loop variables, one letter variables are generally frowned upon. Write the code as if it were to be strange to you if you revisit it in 6 months. Better yet, think of someone else picking up your code in 6 months and trying to understand what it does.

What this may mean is that you will organize your code into many methods, some of which are small and quite singular in purpose. I see an opportunity for such a method here. I found the while loop confusing. In order to find a square root, it seems that you may need a squaring method. In your odd case, the squaring method may only use addition or subtraction.

You should also consider edge cases. For instance, you have no check that S cannot be negative. For a squaring method, there's also cases to consider when an Int32 is squared it may produce a value larger than Int32. Since a number squared cannot be negative, and its larger than a Int32, I will have my method output a UInt64.

public static ulong SquareByAddition(int value)
{
    ulong sum = 0;
    // Convert to ulong once.  
    // Edge case for int.MaxValue where Math.Abs would fail on int.
    // This is fixed by an intermediate cast to long before negating.
    ulong number = (ulong)(value < 0 ? -(long)value : value);
    for (ulong i = 0; i < number; i++)
    {
        sum += number;
    }
    return sum;
}

Note I carefully avoid Math.Abs since it may not be allowed. Furthermore, there is an edge case where int.MinValue will not return an Int32 for its absolute value. I coded around that and used the unary negation.

Performance-wise, a ulong as the index variable can perform slower than an int. A quick change can make it:

public static ulong SquareByAddition2(int value)
{
    ulong sum = 0;
    // Convert to ulong once.  
    // Edge case for int.MaxValue where Math.Abs would fail on int.
    // This is fixed by an intermediate cast to long before negating.
    ulong number = (ulong)(value < 0 ? -(long)value : value);
    var first = (value < 0) ? value : 0;
    var last = (value < 0) ? 0 : value;
    for (var i = first; i < last; i++)
    {
        sum += number;
    }
    return sum;
}

If you protest that the unary negation is not addition or subtraction, you can change it too:

public static ulong SquareByAddition3(int value)
{
    ulong sum = 0;
    // Convert to ulong once.  
    // If you consider negating a value to not be Addition or Subtraction, then 
    // we break up the assigment to number into 2.
    // First, when value is not negative.
    ulong number = (ulong)(value > 0 ? value : 0);
    var first = 0;
    var last = value;
    // Second, when value is negative.  We must be careful around edge case of int.MinValue
    // so we use an intermediate cast to long before subtracting it from 0.
    if (value < 0)
    {
        // Here we technically use subtraction rather than directly negating.
        number = (ulong)(0 - (long)value);
        first = value;
        last = 0;
    }
    for (var i = first; i < last; i++)
    {
        sum += number;
    }
    return sum;
}

So there you have 3 different variations to produce a square by addition. And note that the method name is clear about what it does SquareByAddition.

If I were devising an exercise for beginners, I would ask them to find the integer square root of an input integer because there may not be an answer. Beginners are more comfortable with exact results, so I would have them check if the input integer is a square of an another integer.

But your example doesn't want that. A short method to find the root, if any, for a number follows. It checks that the input is not negative, and reads much better with the SquareByAddition method:

public static void FindSquareRoot(int value)
{
    if (value < 0)
    {
        throw new ArgumentOutOfRangeException(nameof(value), "Input value cannot be negative.");
    }

    // Cast once to ulong
    var number = (ulong)value;

    for (var root = 0; root <= value; root++)
    {
        var square = SquareByAddition(root);
        if (square == number)
        {
            Console.WriteLine($"Square root of {value} is {root}");
            return;
        }
        else if (square > number)
        {
            Console.WriteLine($"Square root of {value} lies between {root - 1} and {root}");
            return;
        }
    }
}

Again, for the record I don't find such exercises practical or educational. Others may feel the same way, which could explain the lack of answers.

\$\endgroup\$
1
\$\begingroup\$
static void FindSquareRoot(int S)

Why void? The method would be more useful if it returned the value rather than printing it, and throw an exception if the input was invalid rather than printing an error message.


    int i = 1;

    for (; i <= S; i++)

The scope of i is the loop, so why not restrict it to that scope?


        int k = S;
        int j = i;

        while (j>0)
        {
            k = k - i;
            j--;
        }

i and j as loop variables are fairly conventional, but what does k mean? It's not a loop variable. A comment indicating that after the inner loop k = S - i * i would help, and might suggest a name like surplus.

Again, restrict the scope of the loop variable to the loop unless there's good reason not to.


Finally, on scope, by pulling k out of the loop you should be able to figure out a way to update its value without using an inner loop...

\$\endgroup\$
2
  • \$\begingroup\$ you mean to declare k variable outside of for loop, yes? \$\endgroup\$
    – Beginner
    Jun 5, 2018 at 15:56
  • \$\begingroup\$ Yes, that's what I mean by pulling [it] out. \$\endgroup\$ Jun 5, 2018 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.