Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #316

Re: Fourth root of integer

Show all headers | View raw

Old Wolf wrote:
> 
> Looking for an algorithm to find the fourth root of
> a large integer (I have a multi-precision integer
> library already). If there is no exact fourth root then
> the floor or ceiling is OK, I don't need a 'remainder'
> or anything.
> 
> Any ideas?

Why not just the square root of the square root?

unsigned fourth_root(unsigned n)
{
    return isqrt(isqrt(n));
}

unsigned isqrt(unsigned n)
{
    unsigned power_of_4, root;

    power_of_4 = ((unsigned)-1 >> 2 - (unsigned)-1 % 3) + 1;
    root = 0;
    do {
        if (n >= root + power_of_4) {
            n -= root + power_of_4;
            root += power_of_4 << 1;
        }
        root >>= 1;
        power_of_4 >>= 2;
    } while (power_of_4 != 0);
    return root;
}

-- 
pete

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Fourth root of integer Old Wolf <oldwolf@inspire.net.nz> - 2011-05-15 20:30 -0700
  Re: Fourth root of integer kym@kymhorsell.com - 2011-05-16 04:10 +0000
    Re: Fourth root of integer Jacob <asdf@hsu.edu> - 2011-05-16 02:49 -0400
  Re: Fourth root of integer pete <pfiland@mindspring.com> - 2011-05-16 09:46 -0400
    Re: Fourth root of integer Charles Richmond <frizzle@tx.rr.com> - 2011-05-16 22:39 -0500
      Re: Fourth root of integer pete <pfiland@mindspring.com> - 2011-05-17 09:17 -0400
  Re: Fourth root of integer rossum <rossum48@coldmail.com> - 2011-05-16 16:41 +0100
  Re: Fourth root of integer Ralph Boland <rpboland@gmail.com> - 2011-05-16 11:06 -0700
  Re: Fourth root of integer Dann Corbit <dcorbit@connx.com> - 2011-05-16 13:28 -0700
    Re: Fourth root of integer Christopher Henrich <chenrich@monmouth.com> - 2011-05-18 23:41 -0400
      Re: Fourth root of integer rossum <rossum48@coldmail.com> - 2011-05-19 09:54 +0100
        Re: Fourth root of integer Christopher Henrich <chenrich@monmouth.com> - 2011-05-20 15:16 -0400
      Re: Fourth root of integer - fourth-root.mws [1/1] Dann Corbit <dcorbit@connx.com> - 2011-05-20 12:42 -0700
        Re: Fourth root of integer - fourth-root.mws [1/1] Christopher Henrich <chenrich@monmouth.com> - 2011-05-20 16:10 -0400
    Re: Fourth root of integer James Waldby <not@valid.invalid> - 2011-05-19 07:01 +0000
      Re: Fourth root of integer James Waldby <not@valid.invalid> - 2011-05-21 00:37 +0000

csiph-web