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>
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

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