Re: Fourth root of integer

Path	csiph.com!x330-a1.tempe.blueboxinc.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail
NNTP-Posting-Date	Mon, 16 May 2011 08:46:10 -0500
Message-ID	<4DD12AA2.2182@mindspring.com> (permalink)
Date	Mon, 16 May 2011 09:46:10 -0400
From	pete <pfiland@mindspring.com>
Reply-To	pfiland@mindspring.com
Organization	PF
X-Mailer	Mozilla 3.04Gold (WinNT; I)
MIME-Version	1.0
Newsgroups	comp.programming
Subject	Re: Fourth root of integer
References	<40fdbc1f-8ca8-47bf-b701-5ca18bb9c3c9@z13g2000prk.googlegroups.com>
Content-Type	text/plain; charset=us-ascii
Content-Transfer-Encoding	7bit
Lines	36
X-Usenet-Provider	http://www.giganews.com
NNTP-Posting-Host	4.154.217.120
X-Trace	sv3-cQoogP2WvDqkzKi8aNwYi/8em0oXpvRgkx2sxs/gGkdT6aZCjq1mUItYi6hs6Tn9wsOciPrewv0+Q3Z!A/oDw6bTzz10J9xi3U6L8QOM9sHzXbMlHBiTorXkNBDM0uw20FEdPxPTdFLDxn6wYQy8HmW+FiBi!6kZ4zoSXh28=
X-Abuse-and-DMCA-Info	Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info	Otherwise we will be unable to process your complaint properly
X-Postfilter	1.3.40
X-Original-Bytes	1851
Xref	x330-a1.tempe.blueboxinc.net comp.programming:316

Show key headers only | 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

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