0

my problem is creating a sqrt function for integer via Scala

f.e.: sqrt ( 26 ) = 6 , s² >= n sqrt (0) = 0, sqrt (1) = 1, sqrt (2) = 2, sqrt (3) = 2, sqrt (4) = 2, sqrt (5) to sqrt (9) = 3 ....

here is my code i came up with:

def sqrt (n: Int): Int = {          

  def sq (a: Int, n: Int): Int = {
    val b = (a + n) / 2
    val c = (b + n / b) / 2
    if (b * b == n) b 
    else if (b * b < n) b + 1
    else c 
  }
  if (n == 0 || n == 1) n else sq (0 , n)       
}

however it doesn't work with all the numbers n >= 0. f.e.: for 6 its 2, how do i tweak my formula?

manonmars
  • 55
  • 2
  • 11
  • So you whan to return result as integer as well ?? – Pavel Dec 03 '16 at 17:40
  • 2
    The square root of 6 **is** 2, if the result is supposed to be an `Int`. What result did you expect? – jwvh Dec 03 '16 at 17:40
  • my expected result is 3, because it needs to meet the condition of s² >= n. because 2² !>= 6. – manonmars Dec 03 '16 at 17:43
  • Please write the test cases for the task first. It will be much easier to test if you get what expected. – Pavel Dec 03 '16 at 17:44
  • edited my question: the sqrt for 10 to 16 should be 4, 17 to 25 it's 5 and so on. and yes everything in integer :/ – manonmars Dec 03 '16 at 17:54
  • The question title mentions recursion. There is no recursion in the code. Is the title wrong or is the code supposed to be recursive? And why is the zero value `a` a passed parameter? It's always zero. Why pass it in? – jwvh Dec 03 '16 at 17:56
  • my title is wrong, sorry for that, edited. it's given in our task to create a function with sqr ( a: Int, n: Int) and return sqr (0,n), i know its useless but my professor want it that way. sorry for the confusion. – manonmars Dec 03 '16 at 18:03
  • Your assignment makes no sense. The simple solution is `math.sqrt(n).ceil.toInt`. Done. – jwvh Dec 03 '16 at 18:12
  • 1
    This is to learn scala. Its a classical task to learn scala. See my updated answer below. But still not sure why you need function signature to be Int -> Int? – Pavel Dec 03 '16 at 18:14
  • my professor probably want us to learn it via the newton method. here is a link i found using python [link](http://stackoverflow.com/questions/15390807/integer-square-root-in-python?rq=1) it is similar to what i did but, he is using a while - loop, which we are not allowed to use. – manonmars Dec 03 '16 at 18:17
  • 1
    It is a newtons method below:) try just spend some time playing with the code below. Try different corner cases etc. – Pavel Dec 03 '16 at 18:19
  • sorry but I am still beginner level so your code doesnt make any sense to me, and we are still using Kojo in school so thanks anyways – manonmars Dec 03 '16 at 18:35

4 Answers4

0

Try change type to Double. Result should be obvious.

 object Math {

  def roundUp(d: Double) = math.ceil(d).toInt

  def abs(x: Double) = if (x < 0) -x else x

  def sqrt(x: Double) = roundUp( sqrtIter(1.0, x) )

  def sqrtIter(guess: Double, x: Double): Double =
    if (isGoodEnough(guess, x)) guess
    else sqrtIter(improve(guess, x), x)

  def isGoodEnough(guess: Double, x: Double) =
    abs(guess * guess - x) < .01

  def improve(guess: Double, x: Double) =
    (guess + x / guess) / 2
}

val r = Math.sqrt(24)
Pavel
  • 1,519
  • 21
  • 29
0
    def sqrt (n: Int): Int = {

    def sq (a: Int, n: Int): Int = if (a * a >= n) a else sq (a+1 , n)

    if (sq (0 , n) * sq (0 , n) >= n) sq (0 , n) else sqrt (sq (0 , n))
    }

here is an easy and nice solution.

manonmars
  • 55
  • 2
  • 11
  • The last line is pointless. The `if` condition is never `false` so the `else` clause is never executed. – jwvh Dec 03 '16 at 20:57
  • `def sqrt(n: Int): Int = (0 to n).dropWhile(x => x*x < n).head` – jwvh Dec 03 '16 at 21:06
  • @manonmars Your solution doesn't properly handle negative numbers. Here it is Scastie: https://scastie.scala-lang.org/EInJFwJ6Rj2f1ydAW4yZiQ – chaotic3quilibrium Mar 13 '22 at 23:05
  • @jwvh Your solution creates a `NoSuchElementException` when passed negative numbers. Here it is in Scastie: https://scastie.scala-lang.org/BBPVTjA4RVGoIAHmL1TQZw – chaotic3quilibrium Mar 13 '22 at 23:06
0

I have added minor improvements to Pavel's Code: roundUp function does not really add up and it gives the wrong results. As square root values will mostly contain decimals, I have limited the decimal by 2 digits. 

def trim(d:Double) = "%1.2f".format(d)

def sqrt(x: Double) =  trim( sqrtIter(1.0, x) ) //(replace /**roundUp**/ with trim)
Unheilig
  • 16,196
  • 193
  • 68
  • 98
kolli
  • 1
0

Technically, there are two solutions. One for the floor value (nearest x: Int where x * x <= n). And the other is the ceiling value (nearest x: Int where x * x >= n).

In your specific case, it appears you are asking for the ceiling.

Floor:

def squareRootFloor(value: Int): Option[Int] =
  if (value > -1)
    Some(
      if (value < 4)
        if (value < 2)
          value
        else
          1
      else {
        def recursive(factor: Int = 2, sqHigh: Int = 9): Int =
          if (value < sqHigh)
            factor
          else
            if (value == sqHigh)
              factor + 1
            else {
              val newFactorHigh = factor + 2
              recursive(factor + 1, newFactorHigh * newFactorHigh)
            }
        recursive()
      }
    )
  else
    None

View/Execute in Scastie

Ceiling:

def squareRootCeiling(value: Int): Option[Int] =
  if (value > -1)
    Some(
      if (value < 5)
        if (value < 2)
          value
        else
          2
      else {
        def recursive(factor: Int = 3, sqHigh: Int = 9): Int =
          if (value <= sqHigh)
            factor
          else {
            val newFactorHigh = factor + 1
            recursive(newFactorHigh, newFactorHigh * newFactorHigh)
          }
        recursive()
      }
    )
  else
    None

View/Execute in Scastie

chaotic3quilibrium
  • 5,661
  • 8
  • 53
  • 86