2

I was researching algorithm of finding primal numbers and saw the statement below, I don't get why.

while (k*k <= n)

is better than 

while (k <= Math.sqrt(n))

Is it because of function call? That calling function uses more resources.

Update: As @Codor said I think I need to mention that k is changed inside loop, while nis not changed.

So if I store Math.sqrt(n) before and use it every time, will it be more efficient than multiplying each time k*k?

Hatik
  • 1,139
  • 1
  • 15
  • 33
  • 5
    simple multiplication of `k*k` will be much faster than calculating square-root of a number. – TheVillageIdiot Apr 16 '18 at 05:08
  • Which language is this? C#? – Codor Apr 16 '18 at 05:09
  • @Codor this is C# but I believe, it doesn't make much difference? – Hatik Apr 16 '18 at 05:10
  • 2
    "So if I store Math.sqrt(n) before and use it every time, will it be more efficient than multiplying each time k*k?" Yes, Definitely. One is calling the whole function while other is just accessing a variable. – Anand Undavia Apr 16 '18 at 06:23
  • @Hatik I am using `2^(m/2)` where `2^m<=n` instead of `sqrt(n)` see [Prime numbers by Eratosthenes quicker sequential than concurrently?](https://stackoverflow.com/a/22477240/2521214) if you store `sqrt` before loop than sqrt should be faster but that depends on the `n` architecture and other stuff too so it also might not. – Spektre Apr 16 '18 at 07:16

2 Answers2

3

Apparently the call to Math.sqrt uses floating-point math, which might be more costly than the integer math used in the multiplication. On the other hand, Math.sqrt needs only one evaluation for the loop, while the evaluation of k*k needs several evaluations.

Codor
  • 17,447
  • 9
  • 29
  • 56
  • 4
    looking at `IL` `Math.Sqrt` is called over every iteration as well – TheVillageIdiot Apr 16 '18 at 05:25
  • I do not code in JAVA at all but does not JAVA use floats for everything (even for integers)? Or it was different language I mistaken this for... but yes sqrt is much more expensive than multiplication unless advanced and or **Quake3 style magic** approaches are used. For example if this [How to get a square root for 32 bit input in one clock cycle only?](https://stackoverflow.com/a/34657972/2521214) is hardcoded into silicon could beat many things as it does not need even multiply ... – Spektre Apr 16 '18 at 07:26
  • 1
    @TheVillageIdiot What is meant is that it is sufficient to evaluate sqrt(n) once, not that it is actually the case... – Jean-Baptiste Yunès Apr 16 '18 at 13:53
2

Let us look at their time complexity for iterations:

  • i=2 .. i*iO(sqrt(n))
  • i=2 .. sqrt(n) O(sqrt(n)*log(n))
  • i=2 .. sqrt (by Newton's method) O(sqrt(n)) + O(log(n))
  • i=2 .. sqrt (by Math.sqrt) O(sqrt(n))

But as you edited, the pre-computed square root is more efficient than the multiplication that must be done each time around the loop.

Abhishek Keshri
  • 3,074
  • 14
  • 31