Re: better return type for usqrt() in factor(6)

[Otto Moerbeek]

On Thu, Sep 01, 2016 at 06:36:15AM +0100, Theo Buehler wrote:

> In factor(6), there is the line
> 
> 216   stop = usqrt(val) + 1;
> 
> where the u_int64_t stop is the upper bound for the sieve of
> Eratosthenes (I cautiously added 1 to be sure to be on the safe side).
> Unfortunately, the right hand side may now overflow for large enough
> val because my brilliant former self chose usqrt() to be of type
> u_int32_t usqrt(u_sqrt64_t); ...
> 
> Example from http://cvsweb.netbsd.org/bsdweb.cgi/src/games/primes/pattern.c
> 
> $ printf "%u\n" $((139646831 * 132095686967))
> 18446744073709551577
> $ factor 18446744073709551577
> 18446744073709551577
> 
> With the patch below:
> 
> $ obj/factor
> 18446744073709551577: 139646831 132095686967
> 
> as it should be.

ok, 

-Otto

> 
> Index: factor.c
> ===
> RCS file: /var/cvs/src/games/factor/factor.c,v
> retrieving revision 1.29
> diff -u -p -r1.29 factor.c
> --- factor.c  14 Aug 2016 18:34:48 -  1.29
> +++ factor.c  1 Sep 2016 04:56:00 -
> @@ -75,7 +75,7 @@ extern const int pattern_size;
>  
>  static void  pr_fact(u_int64_t); /* print factors of a value */
>  static void  pr_bigfact(u_int64_t);
> -static u_int32_t usqrt(u_int64_t);
> +static u_int64_t usqrt(u_int64_t);
>  static void __dead   usage(void);
>  
>  int
> @@ -284,7 +284,7 @@ pr_bigfact(u_int64_t val) /* Factor this
>  }
>  
>  /* Code taken from ping.c */
> -static u_int32_t
> +static u_int64_t
>  usqrt(u_int64_t n)
>  {
>   u_int64_t y, x = 1;
> @@ -299,7 +299,7 @@ usqrt(u_int64_t n)
>   x /= 2;
>   } while (((y < x) && (x - y) > 1) || (y - x) > 1);
>  
> - return (u_int32_t)x;
> + return x;
>  }
>  
>  static void __dead

Re: better return type for usqrt() in factor(6)

[Tom Cosgrove]

ok tom@

>>> Theo Buehler 1-Sep-16 06:36 >>>
>
> In factor(6), there is the line
>
> 216   stop = usqrt(val) + 1;
>
> where the u_int64_t stop is the upper bound for the sieve of
> Eratosthenes (I cautiously added 1 to be sure to be on the safe side).
> Unfortunately, the right hand side may now overflow for large enough
> val because my brilliant former self chose usqrt() to be of type
> u_int32_t usqrt(u_sqrt64_t); ...
>
> Example from http://cvsweb.netbsd.org/bsdweb.cgi/src/games/primes/pattern.c
>
> $ printf "%u\n" $((139646831 * 132095686967))
> 18446744073709551577
> $ factor 18446744073709551577
> 18446744073709551577
>
> With the patch below:
>
> $ obj/factor
> 18446744073709551577: 139646831 132095686967
>
> as it should be.
>
> Index: factor.c
> ===
> RCS file: /var/cvs/src/games/factor/factor.c,v
> retrieving revision 1.29
> diff -u -p -r1.29 factor.c
> --- factor.c  14 Aug 2016 18:34:48 -  1.29
> +++ factor.c  1 Sep 2016 04:56:00 -
> @@ -75,7 +75,7 @@ extern const int pattern_size;
>  
>  static void  pr_fact(u_int64_t); /* print factors of a value */
>  static void  pr_bigfact(u_int64_t);
> -static u_int32_t usqrt(u_int64_t);
> +static u_int64_t usqrt(u_int64_t);
>  static void __dead   usage(void);
>  
>  int
> @@ -284,7 +284,7 @@ pr_bigfact(u_int64_t val) /* Factor this
>  }
>  
>  /* Code taken from ping.c */
> -static u_int32_t
> +static u_int64_t
>  usqrt(u_int64_t n)
>  {
>   u_int64_t y, x = 1;
> @@ -299,7 +299,7 @@ usqrt(u_int64_t n)
>   x /= 2;
>   } while (((y < x) && (x - y) > 1) || (y - x) > 1);
>  
> - return (u_int32_t)x;
> + return x;
>  }
>  
>  static void __dead

Re: better return type for usqrt() in factor(6)

[Philip Guenther]

On Thu, Sep 1, 2016 at 6:36 AM, Theo Buehler  wrote:
> In factor(6), there is the line
>
> 216 stop = usqrt(val) + 1;
>
> where the u_int64_t stop is the upper bound for the sieve of
> Eratosthenes (I cautiously added 1 to be sure to be on the safe side).
> Unfortunately, the right hand side may now overflow for large enough
> val because my brilliant former self chose usqrt() to be of type
> u_int32_t usqrt(u_sqrt64_t); ...

Yeah, it might seem that square-root of a 64bit number should fit in
32bits, but nope, there's a range at the top where the square-root
takes 33bits.

ok guenther@

better return type for usqrt() in factor(6)

[Theo Buehler]

In factor(6), there is the line

216 stop = usqrt(val) + 1;

where the u_int64_t stop is the upper bound for the sieve of
Eratosthenes (I cautiously added 1 to be sure to be on the safe side).
Unfortunately, the right hand side may now overflow for large enough
val because my brilliant former self chose usqrt() to be of type
u_int32_t usqrt(u_sqrt64_t); ...

Example from http://cvsweb.netbsd.org/bsdweb.cgi/src/games/primes/pattern.c

$ printf "%u\n" $((139646831 * 132095686967))
18446744073709551577
$ factor 18446744073709551577
18446744073709551577

With the patch below:

$ obj/factor
18446744073709551577: 139646831 132095686967

as it should be.

Index: factor.c
===
RCS file: /var/cvs/src/games/factor/factor.c,v
retrieving revision 1.29
diff -u -p -r1.29 factor.c
--- factor.c14 Aug 2016 18:34:48 -  1.29
+++ factor.c1 Sep 2016 04:56:00 -
@@ -75,7 +75,7 @@ extern const int pattern_size;
 
 static voidpr_fact(u_int64_t); /* print factors of a value */
 static voidpr_bigfact(u_int64_t);
-static u_int32_t   usqrt(u_int64_t);
+static u_int64_t   usqrt(u_int64_t);
 static void __dead usage(void);
 
 int
@@ -284,7 +284,7 @@ pr_bigfact(u_int64_t val)   /* Factor this
 }
 
 /* Code taken from ping.c */
-static u_int32_t
+static u_int64_t
 usqrt(u_int64_t n)
 {
u_int64_t y, x = 1;
@@ -299,7 +299,7 @@ usqrt(u_int64_t n)
x /= 2;
} while (((y < x) && (x - y) > 1) || (y - x) > 1);
 
-   return (u_int32_t)x;
+   return x;
 }
 
 static void __dead