Bash/solution_1: improve integer square root

PlummersSoftwareLLC / Primes

Prime Number Projects in C#/C++/Python

https://plummerssoftwarellc.github.io/PrimeView/

2.46k stars 573 forks source link

Bash/solution_1: improve integer square root #832

Closed lilweege closed 2 years ago

lilweege commented 2 years ago

Description

Replace brute force linear search square root function with binary search square root. Improves the complexity from n to lg(n). This is to make up for the fact that bash lacks a native math square root. In theory this is vastly superior to the brute force, in practice however there are other bottlenecks which only makes this improvement marginal (on my machine at least).

Contributing requirements

[x] I read the contribution guidelines in CONTRIBUTING.md.
[x] I placed my solution in the correct solution folder.
[x] I added a README.md with the right badge(s).
[x] I added a Dockerfile that builds and runs my solution.
[x] I selected drag-race as the target branch.
[x] All code herein is licensed compatible with BSD-3.

rbergen commented 2 years ago

@lilweege Thanks for contributing! Personally, I like this approach to calculating the sqrt, and I'd be happy to merge it.

@Nitepone, would you agree?

Nitepone commented 2 years ago

Great add! Only nit I have is that I would prefer usage of '[[' over '['.

Bash's test syntax can be faster in some cases afaik, and we aren't striving for posix compliance.

rbergen commented 2 years ago

I actually think using the compound command [[ will make it an even more Bashy approach.

@lilweege Would you be able to update your PR to incorporate this change?

lilweege commented 2 years ago

@rbergen I've implemented the change (and simplified the logic slightly).

I suppose now it could also become something like the following, but I'm not sure if that's better.

[[ $((mid*mid)) -le $2 ]] && ((lo=mid+1)) || ((hi=mid-1))

rbergen commented 2 years ago

@lilweege Thanks for your quick response.

I suppose now it could also become something like the following, but I'm not sure if that's better.

I think this is more of a matter of personal preference, but to me that code starts to look like an entry for a "most illegible code" contest. I do use the [[ <test> ]] && <command> construct every now and then, but stop before using it to implement "if, then, else". Based on that, I would leave the code as it is now. But again, that's just my opinion.

lilweege commented 2 years ago

Performance implications aside, I agree that it could be considered less legible. Other than that, is there anything else? If not, feel free to merge.