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

Groups > comp.programming > #346

Re: Fourth root of integer

Show all headers | View raw

On Thu, 19 May 2011 07:01:14 +0000, James Waldby wrote:
> On Mon, 16 May 2011 13:28:29 -0700, Dann Corbit wrote:
>>  oldwolf@inspire.net.nz says...
>>> 
>>> 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.
> ...
>> Assuming you can get any sort of decent estimate of the root, you can
>> implement this root polisher in multiple precision:
[snip equation]
> [snip code and sample output]
> [...] in multiple precision arithmetic, even a
> single iteration of the above may be slower than just finding the square
> root twice.  Typical MP packages use efficient square root computations
> that take slightly longer than a single divide.
> 
> For example, on my computer using mpfr (gmp) and with default precision
> 256 bits, one iteration of xprimeB takes ~ 3.8 times as long as 2
> mpfr_sqrt calls.  Here are some times, in seconds per half-million
> passes.  DeltaI is t_I-t_1.
> 
> I   Item          t_I
> 1. Empty loop:  0.247415   Passes: 500000
> 2. 2-Sqrt:      1.015866   Delta2:  0.768451
> 3. xprimeB:     3.172006   Delta3:  2.924591
> 4. divide:      0.500479   Delta4:  0.253064
> (t_3-t_1)/(t_2-t_1):   3.805826
> 
[snip explanations of loops]

Since OP wants 4th roots of integers, I recoded program from mpfr to
gmp (ie, using calls like mpz_sqrt, mpz_div, mpz_mul rather than 
mpfr_sqrt, mpfr_div, mpfr_mul) and got the following timings, for
the cases where the 4th powers are 128-bit numbers (like in the 
mpfr test results above) and 256-bit numbers:

I   Item          t_I      Bits:    128
1. Empty loop:  0.062849   Passes:  500000
2. 2-Sqrt:      0.348615   Delta2:  0.285766
3. xprimeB:     1.949296   Delta3:  1.886447
4. divide:      0.136300   Delta4:  0.073451
(t_3-t_1)/(t_2-t_1):    6.601371
(t_2-t_1)/(t_4-t_1):    3.890576

I   Item          t_I      Bits:    256
1. Empty loop:  0.126367   Passes:  500000
2. 2-Sqrt:      0.575044   Delta2:  0.448677
3. xprimeB:     4.153543   Delta3:  4.027176
4. divide:      0.286537   Delta4:  0.160170
(t_3-t_1)/(t_2-t_1):    8.975670
(t_2-t_1)/(t_4-t_1):    2.801253

In the latter case, in each of 4 loops, the same 500000 random 
64-bit numbers were each raised to the 4th power, and treated 
as follows:  Loop 1: nothing else; Loop 2: 2 square roots;  
Loop 3: 1 pass of xprimeB from Dann Corbit's post; Loop 4: 
4th power divided by 2nd power.  The two ratios show that 1 
pass of xprimeB took about 9 times as long as extracting 2 
square roots, and that  extracting 2 square roots took about
3 times as long as 1 divide.

-- 
jiw

Back to comp.programming | Previous | Next — Previous 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