Hello all,

I thought I might try and learn some mathematics, maybe try some of
the Euler problems. Several I've noticed involve finding primes, and I
thought I might try to find a fast way of finding square roots to
integers.

My math (and forth!) skills unfortunately leave a lot to be desired so
I am unsure on the best way to implement this. I have to admit I stole
this algorithm from wikipedia:

public static int sqrt(int num) {
int op = num;
int res = 0;
int one = 1 << 14; // The second-to-top bit is set: 1L<<30 for
long

// "one" starts at the highest power of four <= the argument.
while (one > op)
one >>= 2;

Robert Spykerman gmail.com> writes Re: what is the fastest way of finding an integer square root?

The fastest way to find them is too look them up, or at least to use
memoization.

[..]

[..]

The fastest and best way to do it is (check the CLF archives)
: SQRT ( n1 -- n2 ) S>F FSQRT F>S ;

On May 24, 4:27 pm, m...@iae.nl (Marcel Hendrix) wrote:

I'll keep that in mind if it ever becomes necessary, it's a bit
involved I guess.

Thank you! Didn't think of using the fpu *duh!* That's what I will do.

By the way I found one more algorithm that's quite succinct if one has
no fpu:

\ from Paul E Bennet comp.arch.embedded 4 May 2008
: sqrt -1 TUCK DO 2 + DUP +LOOP 2/ ;

Thanks again

On May 24, 4:27 pm, m...@iae.nl (Marcel Hendrix) wrote:

I'll keep that in mind if it ever becomes necessary, it's a bit
involved I guess.

Thank you! Didn't think of using the fpu *duh!* That's what I will do.

By the way I found one more algorithm that's quite succinct if one has
no fpu:

\ from Paul E Bennet comp.arch.embedded 4 May 2008
: sqrt -1 TUCK DO 2 + DUP +LOOP 2/ ;

Thanks again

Robert Spykerman gmail.com> writes Re: what is the fastest way of finding an integer square root?

[..]

No, it's very simple (for single argument functions). You *will* need
memoization for some of the more difficult highly recursive Euler
problems. These are designed such that naive recursive approaches
fail.

The iForth distribution has several examples of this technique (not
only in the Euler directory). Brad Eckert did discuss it in CLF.

In article w8g2000prd.googlegroups.com>,
Robert Spykerman gmail.com> wrote:

On May 24, 12:23 am, Robert Spykerman gmail.com>
wrote:

Depending on what you want to use the sqrt for, if you dont mind a
little error, you can consider a common inv-sqrt function used in
games:

On May 24, 12:50 pm, "Jeff M." gmail.com> wrote:

On May 23, 10:23 pm, Robert Spykerman gmail.com>
wrote:

This algorithm is often attributed to Dijkstra, which makes for easier
Googling. It doesn't map well to C, though. Here's what I use as a
template for assembly versions:

Here's another version that I found simple enough for machineForth:

\ isqrt.mf translated by Dennis Ruffer 04 Oct 06
\
\ from James Ulery's Computing Integer Square Roots
\ http://www.azillionmonkeys.com/qed/ulerysqroot.pdf

\ /* C version by Jim Ulery */
\ static unsigned julery_isqrt(unsigned long val) {
\ unsigned long temp, g=0, b = 0x8000, bshft = 15;
\ do {
\ if (val >= (temp = (((g << 1) + b)< \ g += b;
\ val -= temp;
\ }
\ } while (b >>= 1);
\ return g;
\ }

[defined] TestCase [IF] simUnit: testISqrt-XX-XXX ( -- method )

[defined] min-isqrt 0= [IF] \ we only want one of this