This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.35 in repository libmath-prime-util-perl.
commit 6b63be20ca4ca868f83a352887a0ace21c8f2daf Author: Dana Jacobsen <d...@acm.org> Date: Thu Dec 5 10:55:43 2013 -0800 Put icbrt in util.h --- lehmer.c | 57 ++++++++++++++++++++------------------------------------- lmo.c | 16 +--------------- util.h | 22 ++++++++++++++++++++++ 3 files changed, 43 insertions(+), 52 deletions(-) diff --git a/lehmer.c b/lehmer.c index 368d194..4e6488f 100644 --- a/lehmer.c +++ b/lehmer.c @@ -130,8 +130,7 @@ typedef signed long IV; #define prime_precalc(n) /* */ #define BITS_PER_WORD ((ULONG_MAX <= 4294967295UL) ? 32 : 64) -static UV isqrt(UV n) -{ +static UV isqrt(UV n) { UV root; if (sizeof(UV) == 8 && n >= 18446744065119617025UL) return 4294967295UL; if (sizeof(UV) == 4 && n >= 4294836225UL) return 65535UL; @@ -140,6 +139,24 @@ static UV isqrt(UV n) while ((root+1)*(root+1) <= n) root++; return root; } +static UV icbrt(UV n) { + UV b, root = 0; + int s; + if (sizeof(UV) == 8) { + s = 63; if (n >= 18446724184312856125UL) return 2642245UL; + } else { + s = 30; if (n >= 4291015625UL) return 1625UL; + } + for ( ; s >= 0; s -= 3) { + root += root; + b = 3*root*(root+1)+1; + if ((n >> s) >= b) { + n -= b << s; + root++; + } + } + return root; +} /* Callback used for creating an array of primes. */ static uint32_t* sieve_array = 0; @@ -198,6 +215,7 @@ static uint32_t* generate_small_primes(UV n) /* We will use pre-sieving to speed up counting for small ranges */ #define SIEVE_MULT 1 +#define FUNC_icbrt 1 #include "lehmer.h" #include "util.h" #include "cache.h" @@ -233,42 +251,7 @@ static uint32_t* generate_small_primes(UV n) if (verbose > 1) printf("generated %lu small primes, from 2 to %lu\n", i, (unsigned long)primes[i]); return primes; } - -#endif - -static UV icbrt(UV n) -{ - UV root = 0; - /* int s = BITS_PER_WORD - (BITS_PER_WORD % 3); */ -#if BITS_PER_WORD == 32 - int s = 30; - if (n >= UVCONST(4291015625)) return UVCONST(1625); -#else - int s = 63; - if (n >= UVCONST(18446724184312856125)) return UVCONST(2642245); -#endif -#if 0 - /* The integer cube root code is about 30% faster for me */ - root = (UV) pow(n, 1.0/3.0); - if (root*root*root > n) { - root--; - while (root*root*root > n) root--; - } else { - while ((root+1)*(root+1)*(root+1) <= n) root++; - } -#else - for ( ; s >= 0; s -= 3) { - UV b; - root += root; - b = 3*root*(root+1)+1; - if ((n >> s) >= b) { - n -= b << s; - root++; - } - } #endif - return root; -} /* Given an array of primes[1..lastprime], return Pi(n) where n <= lastprime. diff --git a/lmo.c b/lmo.c index eb37c8d..7fcf321 100644 --- a/lmo.c +++ b/lmo.c @@ -56,6 +56,7 @@ /* Phi sieve multiplier, adjust for best performance */ #define PHI_SIEVE_MULT 13 +#define FUNC_icbrt 1 #include "lmo.h" #include "util.h" #include "cache.h" @@ -65,21 +66,6 @@ typedef unsigned char uint8; typedef unsigned short uint16; typedef uint32_t uint32; -static UV icbrt(UV n) { - UV b, root = 0; - int s = 63; - if (n >= UVCONST(18446724184312856125)) return UVCONST(2642245); - for (; s >= 0; s -= 3) { - root += root; - b = 3*root*(root+1)+1; - if ((n >> s) >= b) { - n -= b << s; - root++; - } - } - return root; -} - static const unsigned char byte_ones[256] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, diff --git a/util.h b/util.h index efc4107..15fd457 100644 --- a/util.h +++ b/util.h @@ -47,6 +47,28 @@ static UV isqrt(UV n) { return root; } +#ifdef FUNC_icbrt +static UV icbrt(UV n) { + UV b, root = 0; +#if BITS_PER_WORD == 32 + int s = 30; + if (n >= UVCONST(4291015625)) return UVCONST(1625); +#else + int s = 63; + if (n >= UVCONST(18446724184312856125)) return UVCONST(2642245); +#endif + for ( ; s >= 0; s -= 3) { + root += root; + b = 3*root*(root+1)+1; + if ((n >> s) >= b) { + n -= b << s; + root++; + } + } + return root; +} +#endif + #ifdef FUNC_gcd_ui static UV gcd_ui(UV x, UV y) { UV t; -- Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-perl/packages/libmath-prime-util-perl.git _______________________________________________ Pkg-perl-cvs-commits mailing list Pkg-perl-cvs-commits@lists.alioth.debian.org http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-perl-cvs-commits