Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/games Imported and adapted from FreeBSD svn r272166 and r272...
details: https://anonhg.NetBSD.org/src/rev/4f43adadabd8
branches: trunk
changeset: 802810:4f43adadabd8
user: ast <ast%NetBSD.org@localhost>
date: Thu Oct 02 21:36:37 2014 +0000
description:
Imported and adapted from FreeBSD svn r272166 and r272207; this fixes
false positives for products of primes larger than 2^16. For example,
before this commit:
$ /usr/games/primes 4295360521 4295360522
4295360521
but
$ /usr/games/factor 4295360521
4295360521: 65539 65539
or
$ /usr/games/primes 3825123056546413049 3825123056546413050
3825123056546413049
yet
$ /usr/games/factor 3825123056546413049
3825123056546413049: 165479 23115459100831
or
$ /usr/games/primes 18446744073709551577
18446744073709551577
although
$ /usr/games/factor 18446744073709551577
18446744073709551577: 139646831 132095686967
Incidentally, the above examples show the smallest and largest cases that
were erroneously stated as prime in the range 2^32 .. 3825123056546413049
.. 2^64; the primes(6) program now stops at 3825123056546413050 as
primality tests on larger integers would be by brute force factorization.
In addition, special to the NetBSD version:
. for -d option, skip first difference when start is >65537 as it is incorrect
. corrected usage to mention both the existing -d as well as the new -h option
For original FreeBSD commit message by Colin Percival, see:
http://svnweb.freebsd.org/base?view=revision&revision=272166
diffstat:
games/factor/factor.6 | 17 +--
games/factor/factor.c | 16 +--
games/primes/Makefile | 4 +-
games/primes/pattern.c | 13 +-
games/primes/pr_tbl.c | 16 ++--
games/primes/primes.6 | 42 +++++++---
games/primes/primes.c | 129 +++++++++++++++-----------------
games/primes/primes.h | 36 +++++++-
games/primes/spsp.c | 195 +++++++++++++++++++++++++++++++++++++++++++++++++
9 files changed, 344 insertions(+), 124 deletions(-)
diffs (truncated from 843 to 300 lines):
diff -r cfc442c84ac0 -r 4f43adadabd8 games/factor/factor.6
--- a/games/factor/factor.6 Thu Oct 02 21:29:44 2014 +0000
+++ b/games/factor/factor.6 Thu Oct 02 21:36:37 2014 +0000
@@ -1,4 +1,4 @@
-.\" $NetBSD: factor.6,v 1.12 2010/05/15 21:22:39 joerg Exp $
+.\" $NetBSD: factor.6,v 1.13 2014/10/02 21:36:37 ast Exp $
.\"
.\" Copyright (c) 1989, 1993
.\" The Regents of the University of California. All rights reserved.
@@ -33,9 +33,7 @@
.\" @(#)factor.6 8.1 (Berkeley) 5/31/93
.\"
.\"
-.\" By: Landon Curt Noll chongo%toad.com@localhost, ...!{sun,tolsoft}!hoptoad!chongo
-.\"
-.\" chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
+.\" By Landon Curt Noll, http://www.isthe.com/chongo/index.html /\oo/\
.\"
.Dd May 15, 2010
.Dt FACTOR 6
@@ -88,10 +86,7 @@
.Vt unsigned long .
.Sh DIAGNOSTICS
Out of range or invalid input results in
-an appropriate error message
-being written to standard error.
-.\".Sh BUGS
-.\".Nm
-.\"cannot handle the
-.\".Dq 10 most wanted
-.\"factor list.
+an appropriate error message to standard error.
+.Sh AUTHORS
+Originally by
+.An Landon Curt Noll .
diff -r cfc442c84ac0 -r 4f43adadabd8 games/factor/factor.c
--- a/games/factor/factor.c Thu Oct 02 21:29:44 2014 +0000
+++ b/games/factor/factor.c Thu Oct 02 21:36:37 2014 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: factor.c,v 1.26 2011/11/09 20:17:44 drochner Exp $ */
+/* $NetBSD: factor.c,v 1.27 2014/10/02 21:36:37 ast Exp $ */
/*
* Copyright (c) 1989, 1993
@@ -42,16 +42,14 @@
#if 0
static char sccsid[] = "@(#)factor.c 8.4 (Berkeley) 5/4/95";
#else
-__RCSID("$NetBSD: factor.c,v 1.26 2011/11/09 20:17:44 drochner Exp $");
+__RCSID("$NetBSD: factor.c,v 1.27 2014/10/02 21:36:37 ast Exp $");
#endif
#endif /* not lint */
/*
* factor - factor a number into primes
*
- * By: Landon Curt Noll chongo%toad.com@localhost, ...!{sun,tolsoft}!hoptoad!chongo
- *
- * chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
+ * By Landon Curt Noll, http://www.isthe.com/chongo/index.html /\oo/\
*
* usage:
* factor [number] ...
@@ -72,6 +70,7 @@
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
+#include <inttypes.h>
#ifdef HAVE_OPENSSL
#include <openssl/bn.h>
@@ -93,8 +92,7 @@
* We are able to sieve 2^32-1 because this byte table yields all primes
* up to 65537 and 65537^2 > 2^32-1.
*/
-extern const ubig prime[];
-extern const ubig *pr_limit; /* largest prime in the prime array */
+
#if 0 /* debugging: limit table use to stress the "pollard" code */
#define pr_limit &prime[0]
#endif
@@ -198,7 +196,7 @@
static void
pr_fact(BIGNUM *val)
{
- const ubig *fact; /* The factor found. */
+ const uint64_t *fact; /* The factor found. */
/* Firewall - catch 0 and 1. */
if (BN_is_zero(val) || BN_is_one(val))
@@ -239,7 +237,7 @@
/* Divide factor out until none are left. */
do {
- printf(" %lu", *fact);
+ printf(" %" PRIu64, *fact);
BN_div_word(val, (BN_ULONG)*fact);
} while (BN_mod_word(val, (BN_ULONG)*fact) == 0);
diff -r cfc442c84ac0 -r 4f43adadabd8 games/primes/Makefile
--- a/games/primes/Makefile Thu Oct 02 21:29:44 2014 +0000
+++ b/games/primes/Makefile Thu Oct 02 21:36:37 2014 +0000
@@ -1,8 +1,8 @@
-# $NetBSD: Makefile,v 1.7 2004/02/08 13:16:25 jsm Exp $
+# $NetBSD: Makefile,v 1.8 2014/10/02 21:36:37 ast Exp $
# @(#)Makefile 8.1 (Berkeley) 5/31/93
PROG= primes
-SRCS= pattern.c pr_tbl.c primes.c
+SRCS= pattern.c pr_tbl.c primes.c spsp.c
MAN= primes.6
DPADD= ${LIBM}
LDADD= -lm
diff -r cfc442c84ac0 -r 4f43adadabd8 games/primes/pattern.c
--- a/games/primes/pattern.c Thu Oct 02 21:29:44 2014 +0000
+++ b/games/primes/pattern.c Thu Oct 02 21:36:37 2014 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: pattern.c,v 1.6 2003/08/07 09:37:33 agc Exp $ */
+/* $NetBSD: pattern.c,v 1.7 2014/10/02 21:36:37 ast Exp $ */
/*
* Copyright (c) 1989, 1993
@@ -32,21 +32,20 @@
* SUCH DAMAGE.
*/
-#include <sys/cdefs.h>
+#include <sys/types.h>
+
#ifndef lint
#if 0
static char sccsid[] = "@(#)pattern.c 8.1 (Berkeley) 5/31/93";
#else
-__RCSID("$NetBSD: pattern.c,v 1.6 2003/08/07 09:37:33 agc Exp $");
+__RCSID("$NetBSD: pattern.c,v 1.7 2014/10/02 21:36:37 ast Exp $");
#endif
#endif /* not lint */
/*
* pattern - the Eratosthenes sieve on odd numbers for 3,5,7,11 and 13
*
- * By: Landon Curt Noll chongo%toad.com@localhost
- *
- * chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
+ * By Landon Curt Noll, http://www.isthe.com/chongo/index.html /\oo/\
*
* To avoid excessive sieves for small factors, we use the table below to
* setup our sieve blocks. Each element represents a odd number starting
@@ -440,4 +439,4 @@
0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,
0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,0,0,0,0,0,1
};
-const int pattern_size = (sizeof(pattern)/sizeof(pattern[0]));
+const size_t pattern_size = (sizeof(pattern)/sizeof(pattern[0]));
diff -r cfc442c84ac0 -r 4f43adadabd8 games/primes/pr_tbl.c
--- a/games/primes/pr_tbl.c Thu Oct 02 21:29:44 2014 +0000
+++ b/games/primes/pr_tbl.c Thu Oct 02 21:36:37 2014 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: pr_tbl.c,v 1.7 2003/08/07 09:37:33 agc Exp $ */
+/* $NetBSD: pr_tbl.c,v 1.8 2014/10/02 21:36:37 ast Exp $ */
/*
* Copyright (c) 1989, 1993
@@ -37,24 +37,24 @@
#if 0
static char sccsid[] = "@(#)pr_tbl.c 8.1 (Berkeley) 5/31/93";
#else
-__RCSID("$NetBSD: pr_tbl.c,v 1.7 2003/08/07 09:37:33 agc Exp $");
+__RCSID("$NetBSD: pr_tbl.c,v 1.8 2014/10/02 21:36:37 ast Exp $");
#endif
#endif /* not lint */
/*
* prime - prime table
*
- * By: Landon Curt Noll chongo%toad.com@localhost, ...!{sun,tolsoft}!hoptoad!chongo
+ * By Landon Curt Noll, http://www.isthe.com/chongo/index.html /\oo/\
*
- * chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
- *
- * We are able to sieve 2^32-1 because this table has primes up to 65537
+ * We are able to sieve 2^32-1 because this table has primes up to 65537
* and 65537^2 > 2^32-1.
*/
+#include <stddef.h>
+
#include "primes.h"
-const ubig prime[] = {
+const uint64_t prime[] = {
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,
107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,
211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,
@@ -546,4 +546,4 @@
};
/* pr_limit - largest prime in the prime table */
-const ubig *pr_limit = &prime[(sizeof(prime)/sizeof(prime[0]))-1];
+const uint64_t *const pr_limit = &prime[(sizeof(prime)/sizeof(prime[0]))-1];
diff -r cfc442c84ac0 -r 4f43adadabd8 games/primes/primes.6
--- a/games/primes/primes.6 Thu Oct 02 21:29:44 2014 +0000
+++ b/games/primes/primes.6 Thu Oct 02 21:36:37 2014 +0000
@@ -1,4 +1,4 @@
-.\" $NetBSD: primes.6,v 1.3 2008/02/03 03:29:17 wiz Exp $
+.\" $NetBSD: primes.6,v 1.4 2014/10/02 21:36:37 ast Exp $
.\"
.\" Copyright (c) 1989, 1993
.\" The Regents of the University of California. All rights reserved.
@@ -33,9 +33,7 @@
.\" @(#)factor.6 8.1 (Berkeley) 5/31/93
.\"
.\"
-.\" By: Landon Curt Noll chongo%toad.com@localhost, ...!{sun,tolsoft}!hoptoad!chongo
-.\"
-.\" chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
+.\" By Landon Curt Noll, http://www.isthe.com/chongo/index.html /\oo/\
.\"
.Dd February 3, 2008
.Dt PRIMES 6
@@ -46,6 +44,7 @@
.Sh SYNOPSIS
.Nm primes
.Op Fl d
+.Op Fl h
.Op Ar start Op Ar stop
.Sh DESCRIPTION
The
@@ -61,18 +60,18 @@
.Ar stop .
The
.Ar stop
-value must not be greater than 4294967295.
+value must not be greater than 3825123056546413050.
The default value of
.Ar stop
-is 4294967295.
+is 3825123056546413050.
.Pp
When the
.Nm
utility is invoked with no arguments,
.Ar start
-is read from standard input.
+is read from standard input and
.Ar stop
-is taken to be 4294967295.
+is taken to be 3825123056546413050.
The
.Ar start
value may be preceded by a single
@@ -81,15 +80,34 @@
.Ar start
value is terminated by a non-digit character (such as a newline).
The input line must not be longer than 255 characters.
+.Pp
When given the
.Fl d
argument,
.Nm
prints the difference between the current and the previous prime.
+.Pp
+When given the
+.Fl h
+argument,
+.Nm
+prints the prime numbers in hexadecimal.
.Sh DIAGNOSTICS
Out of range or invalid input results in
-an appropriate error message
-being written to standard error.
-.Sh BUGS
+an appropriate error message to standard error.
+.Sh AUTHORS
+Originally by
+.An Landon Curt Noll ,
+extended to some 64-bit primes by
+.An Colin Percival .
+.Sh CAVEATS
+This
.Nm
-won't get you a world record.
+program won't get you a world record.
+.Pp
+The program is not able to list primes between
+3825123056546413050 and 18446744073709551615 (2^64
+- 1) as it relies on strong pseudoprime tests after
+sieving, and it is yet unknown how many of those
+tests are needed to prove primality for integers
+larger than 3825123056546413050.
diff -r cfc442c84ac0 -r 4f43adadabd8 games/primes/primes.c
--- a/games/primes/primes.c Thu Oct 02 21:29:44 2014 +0000
+++ b/games/primes/primes.c Thu Oct 02 21:36:37 2014 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: primes.c,v 1.19 2011/08/30 02:58:04 jakllsch Exp $ */
+/* $NetBSD: primes.c,v 1.20 2014/10/02 21:36:37 ast Exp $ */
/*
* Copyright (c) 1989, 1993
@@ -42,23 +42,23 @@
Home |
Main Index |
Thread Index |
Old Index