Incorrect results concerning "large" primes and Wilson's theorem
Jaroslav Hajek
highegg at gmail.com
Mon Aug 18 00:50:36 CDT 2008
On Wed, Aug 13, 2008 at 10:22 AM, Andrea Franceschini
<andrea.franceschini at gmail.com> wrote:
> Bug report for Octave 3.0.1 configured for i686-pc-linux-gnu
>
> Description:
> -----------
>
> * While I wasn't able to check whether the factorial function
> produced correct results for "large" numbers, I still found an
> evidence of something wrong with very big integers.
> Wilson's theorem I'm referring to is the one that states that
> (let me rephrase it a bit) for p being a prime then
> mod(factorial(p-1),p) = p-1.
> What I found is that this stops working for me after p = 19.
>
> Repeat-By:
> ---------
>
> octave:1> mod(factorial(4), 5)
> ans = 4
> octave:2> mod(factorial(6), 7)
> ans = 6
> octave:3> mod(factorial(10), 11)
> ans = 10
> octave:4> mod(factorial(12), 13)
> ans = 12
> octave:5> mod(factorial(16), 17)
> ans = 16
> octave:6> mod(factorial(18), 19)
> ans = 12
> octave:7> mod(factorial(22), 23)
> ans = 0
> octave:8> mod(factorial(26), 27)
> ans = 0
> octave:9> version
> ans = 3.0.1
>
Octave has no support for big integers. With factorial(22) you are
already losing the trailing digits. Further, factorial won't use
64-bit integers even if your machine has them, presumably to be
compatible with Matlab.
> Fix:
> ---
>
> * I actually don't know where the problem lies, but assuming that the
> functions are properly working, I think it may be in the library that
> manages the big integers. Otherwise it is in the functions.
> As a last resource, it may even be my machine.
>
>
> Configuration (please do not edit this section):
> -----------------------------------------------
>
> uname output: Linux porto 2.6.25-gentoo-r6 #1 PREEMPT Wed Jul 30
> 14:42:58 CEST 2008 i686 Intel(R) Pentium(R) M processor 1.73GHz
> GenuineIntel GNU/Linux
> configure opts: '--prefix=/usr' '--host=i686-pc-linux-gnu'
> '--mandir=/usr/share/man' '--infodir=/usr/share/info'
> '--datadir=/usr/share' '--sysconfdir=/etc' '--localstatedir=/var/lib'
> '--without-hdf5' '--without-curl' '--with-zlib' '--with-fftw'
> '--enable-readline' '--localstatedir=/var/state/octave'
> '--enable-rpath' '--with-blas=blas' '--with-lapack=lapack'
> '--enable-static' '--enable-shared' '--enable-dl' '--without-umfpack'
> '--without-colamd' '--without-ccolamd' '--without-cholmod'
> '--without-cxsparse' '--build=i686-pc-linux-gnu'
> 'build_alias=i686-pc-linux-gnu' 'host_alias=i686-pc-linux-gnu'
> 'CFLAGS=-O2 -march=pentium-m -mtune=pentium-m -pipe
> -fomit-frame-pointer' 'LDFLAGS=-Wl,-s' 'CXXFLAGS=-O2 -march=pentium-m
> -mtune=pentium-m -pipe -fomit-frame-pointer'
> Fortran compiler: i686-pc-linux-gnu-gfortran
> FFLAGS: -O -mieee-fp
> F2C: @F2C@
> F2CFLAGS: @F2CFLAGS@
> FLIBS: -L/usr/lib/gcc/i686-pc-linux-gnu/4.1.2
> -L/usr/lib/gcc/i686-pc-linux-gnu/4.1.2/../../../../i686-pc-linux-gnu/lib
> -L/usr/lib/gcc/i686-pc-linux-gnu/4.1.2/../../.. -lz -lgfortranbegin
> -lgfortran -lm
> CPPFLAGS:
> INCFLAGS: -I. -I. -I./liboctave -I./src -I./libcruft/misc
> C compiler: i686-pc-linux-gnu-gcc, version 4.1.2 (Gentoo 4.1.2 p1.1)
> CFLAGS: -O2 -march=pentium-m -mtune=pentium-m -pipe
> -fomit-frame-pointer
> CPICFLAG: -fPIC
> C++ compiler: i686-pc-linux-gnu-g++, version 4.1.2
> CXXFLAGS: -O2 -march=pentium-m -mtune=pentium-m -pipe
> -fomit-frame-pointer
> CXXPICFLAG: -fPIC
> LD_CXX: i686-pc-linux-gnu-g++
> LDFLAGS: -Wl,-s
> LIBFLAGS: -L.
> RLD_FLAG: -Wl,-rpath -Wl,/usr/lib/octave-3.0.1
> BLAS_LIBS: -llapack -lblas
> FFTW_LIBS: -lfftw3
> LIBS: -lreadline -lncurses -ldl -lz -lm
> LEXLIB:
> LIBGLOB:
> SED: /bin/sed
> DEFS:
>
> -DPACKAGE_NAME="" -DPACKAGE_TARNAME="" -DPACKAGE_VERSION=""
> -DPACKAGE_STRING="" -DPACKAGE_BUGREPORT="" -DOCTAVE_SOURCE=1
> -D_GNU_SOURCE=1 -DSTDC_HEADERS=1 -DHAVE_SYS_TYPES_H=1 -DHAVE_SYS_STAT_H=1
> -DHAVE_STDLIB_H=1 -DHAVE_STRING_H=1 -DHAVE_MEMORY_H=1 -DHAVE_STRINGS_H=1
> -DHAVE_INTTYPES_H=1 -DHAVE_STDINT_H=1 -DHAVE_UNISTD_H=1 -DSEPCHAR=':'
> -DSEPCHAR_STR=":" -D__NO_MATH_INLINES=1 -DCXX_NEW_FRIEND_TEMPLATE_DECL=1
> -DCXX_ISO_COMPLIANT_LIBRARY=1 -DCXX_ABI=gnu_v3 -DHAVE_LIBM=1
> -DHAVE_QHULL=1 -DHAVE_PCRE=1 -DHAVE_REGEXEC=1 -DHAVE_REGEX=1
> -DHAVE_ZLIB_H=1 -DHAVE_ZLIB=1 -DHAVE_FFTW3=1 -DHAVE_GLPK_H=1
> -DHAVE_GLPK=1 -DHAVE_IEEE754_DATA_FORMAT=1 -DF77_FUNC(name,NAME)=name ##
> _ -DF77_FUNC_(name,NAME)=name ## _ -DHAVE_BLAS=1 -DHAVE_GETHOSTNAME=1
> -DHAVE_GETPWNAM=1 -DHAVE_DEV_T=1 -DHAVE_INO_T=1 -DHAVE_NLINK_T=1
> -DHAVE_NLINK_T=1 -DHAVE_LONG_LONG_INT=1 -DHAVE_UNSIGNED_LONG_LONG_INT=1
> -DHAVE_SIGSET_T=1 -DHAVE_SIG_ATOMIC_T=1 -DSIZEOF_SHORT=2
> -DSIZEOF_INT=4 -DSIZEOF_LONG=4 -DSIZEOF_LONG_LONG=8 -DHAVE_ALLOCA_H=1
> -DHAVE_ALLOCA=1 -DNPOS=std::string::npos -DHAVE_PLACEMENT_DELETE=1
> -DHAVE_DYNAMIC_AUTO_ARRAYS=1 -DSTDC_HEADERS=1 -DHAVE_DIRENT_H=1
> -DTIME_WITH_SYS_TIME=1 -DHAVE_SYS_WAIT_H=1 -DHAVE_ASSERT_H=1
> -DHAVE_CURSES_H=1 -DHAVE_DLFCN_H=1 -DHAVE_FCNTL_H=1 -DHAVE_FLOAT_H=1
> -DHAVE_GRP_H=1 -DHAVE_INTTYPES_H=1 -DHAVE_LIMITS_H=1 -DHAVE_LOCALE_H=1
> -DHAVE_MEMORY_H=1 -DHAVE_NCURSES_H=1 -DHAVE_POLL_H=1 -DHAVE_PWD_H=1
> -DHAVE_STDINT_H=1 -DHAVE_STDLIB_H=1 -DHAVE_STRING_H=1 -DHAVE_SYS_IOCTL_H=1
> -DHAVE_SYS_PARAM_H=1 -DHAVE_SYS_POLL_H=1 -DHAVE_SYS_RESOURCE_H=1
> -DHAVE_SYS_SELECT_H=1 -DHAVE_SYS_STAT_H=1 -DHAVE_SYS_TIME_H=1
> -DHAVE_SYS_TIMES_H=1 -DHAVE_SYS_TYPES_H=1 -DHAVE_SYS_UTSNAME_H=1
> -DHAVE_TERMCAP_H=1 -DHAVE_UNISTD_H=1 -DHAVE_UTIME_H=1 -DHAVE_SSTREAM=1
> -DHAVE_TERMIO_H=1 -DHAVE_SGTTY_H=1 -DHAVE_GLOB_H=1 -DHAVE_FNMATCH_H=1
> -DHAVE_FNMATCH=1 -DHAVE_GLOB=1 -DHAVE_ATEXIT=1 -DHAVE_BASENAME=1
> -DHAVE_BCOPY=1 -DHAVE_BZERO=1 -DHAVE_CANONICALIZE_FILE_NAME=1
> -DHAVE_CHMOD=1 -DHAVE_DUP2=1 -DHAVE_ENDGRENT=1 -DHAVE_ENDPWENT=1
> -DHAVE_EXECVP=1 -DHAVE_FCNTL=1 -DHAVE_FORK=1 -DHAVE_GETCWD=1
> -DHAVE_GETEGID=1 -DHAVE_GETEUID=1 -DHAVE_GETGID=1 -DHAVE_GETGRENT=1
> -DHAVE_GETGRGID=1 -DHAVE_GETGRNAM=1 -DHAVE_GETPGRP=1 -DHAVE_GETPID=1
> -DHAVE_GETPPID=1 -DHAVE_GETPWENT=1 -DHAVE_GETPWUID=1 -DHAVE_GETTIMEOFDAY=1
> -DHAVE_GETUID=1 -DHAVE_GETWD=1 -DHAVE_KILL=1 -DHAVE_LGAMMA=1
> -DHAVE_LINK=1 -DHAVE_LOCALTIME_R=1 -DHAVE_LSTAT=1 -DHAVE_MEMMOVE=1
> -DHAVE_MKDIR=1 -DHAVE_MKFIFO=1 -DHAVE_MKSTEMP=1 -DHAVE_ON_EXIT=1
> -DHAVE_PIPE=1 -DHAVE_POLL=1 -DHAVE_PUTENV=1 -DHAVE_RAISE=1
> -DHAVE_READLINK=1 -DHAVE_REALPATH=1 -DHAVE_RENAME=1 -DHAVE_RINDEX=1
> -DHAVE_RMDIR=1 -DHAVE_ROUND=1 -DHAVE_SELECT=1 -DHAVE_SETGRENT=1
> -DHAVE_SETLOCALE=1 -DHAVE_SETPWENT=1 -DHAVE_SETVBUF=1 -DHAVE_SIGACTION=1
> -DHAVE_SIGLONGJMP=1 -DHAVE_SIGPENDING=1 -DHAVE_SIGPROCMASK=1
> -DHAVE_SIGSUSPEND=1 -DHAVE_SNPRINTF=1 -DHAVE_STAT=1 -DHAVE_STRCASECMP=1
> -DHAVE_STRDUP=1 -DHAVE_STRERROR=1 -DHAVE_STRNCASECMP=1 -DHAVE_STRPTIME=1
> -DHAVE_STRSIGNAL=1 -DHAVE_SYMLINK=1 -DHAVE_TEMPNAM=1 -DHAVE_TGAMMA=1
> -DHAVE_UMASK=1 -DHAVE_UNAME=1 -DHAVE_UNLINK=1 -DHAVE_USLEEP=1
> -DHAVE_UTIME=1 -DHAVE_VFPRINTF=1 -DHAVE_VSPRINTF=1 -DHAVE_VSNPRINTF=1
> -DHAVE_WAITPID=1 -DHAVE_STRFTIME=1 -DHAVE_LIBDL=1 -DHAVE_DLOPEN=1
> -DHAVE_DLSYM=1 -DHAVE_DLERROR=1 -DHAVE_DLCLOSE=1 -DHAVE_DLOPEN_API=1
> -DENABLE_DYNAMIC_LINKING=1 -DHAVE_TIMEVAL=1 -DHAVE_FINITE=1
> -DHAVE_ISNAN=1 -DHAVE_ISINF=1 -DHAVE_COPYSIGN=1 -DHAVE_DECL_SIGNBIT=1
> -DHAVE_ACOSH=1 -DHAVE_ASINH=1 -DHAVE_ATANH=1 -DHAVE_ERF=1 -DHAVE_ERFC=1
> -DHAVE_EXP2=1 -DHAVE_LOG2=1 -DHAVE_STRUCT_STAT_ST_BLKSIZE=1
> -DHAVE_STRUCT_STAT_ST_BLOCKS=1 -DHAVE_STRUCT_STAT_ST_RDEV=1
> -DHAVE_STRUCT_TM_TM_ZONE=1 -DHAVE_TM_ZONE=1 -DUSE_READLINE=1
> -DEXCEPTION_IN_MATH=1 -DRETSIGTYPE=void -DHAVE_DECL_SYS_SIGLIST=1
> -DHAVE_POSIX_SIGNALS=1 -DRETSIGTYPE_IS_VOID=1 -DHAVE_GETRUSAGE=1
> -DHAVE_TIMES=1 -DYYTEXT_POINTER=1 -DGNUPLOT_BINARY="gnuplot"
>
> User-preferences (please do not edit this section):
> --------------------------------------------------
>
> EDITOR = /bin/nano
> EXEC_PATH = /usr/libexec/octave/3.0.1/site/exec/i686-pc-linux-gnu:/usr/libexec/octave/api-v32/site/exec/i686-pc-linux-gnu:/usr/libexec/octave/site/exec/i686-pc-linux-gnu:/usr/libexec/octave/3.0.1/exec/i686-pc-linux-gnu:/usr/bin:/usr/local/bin:/usr/bin:/bin:/opt/bin:/usr/i686-pc-linux-gnu/gcc-bin/4.1.2:/usr/kde/3.5/bin:/usr/qt/3/bin:/opt/panda3d/bin:/home/morpheu5/src/android/tools:/opt/java/bin:/home/morpheu5/src/ns/ns-allinone-2.33/bin:/home/morpheu5/src/ns/ns-allinone-2.33/tcl8.4.18/unix:/home/morpheu5/src/ns/ns-allinone-2.33/tk8.4.18/unix:/home/morpheu5/src/ns/ns-allinone-2.33/tclcl
> IMAGE_PATH = .:/usr/share/octave/3.0.1/imagelib
> PAGER = /usr/bin/less
> PS1 = \s:\#>
> PS2 = >
> PS4 = +
> beep_on_error = 0
> completion_append_char =
> crash_dumps_octave_core = 1
> echo_executing_commands = 0
> fixed_point_format = 0
> gnuplot_binary = gnuplot
> gnuplot_command_end =
>
> gnuplot_command_plot = pl
> gnuplot_command_replot = rep
> gnuplot_command_splot = sp
> gnuplot_command_title = t
> gnuplot_command_using = u
> gnuplot_command_with = w
> history_file = /home/morpheu5/.octave_hist
> history_size = 1024
> ignore_function_time_stamp = system
> info_file = /usr/share/info/octave.info
> info_program = info
> makeinfo_program = makeinfo
> max_recursion_depth = 256
> output_max_field_width = 5
> output_precision = 5
> page_output_immediately = 0
> page_screen_output = 1
> print_answer_id_name = 1
> print_empty_dimensions = 1
> save_precision = 16
> saving_history = 1
> sighup_dumps_octave_core = 1
> sigterm_dumps_octave_core = 1
> silent_functions = 0
> split_long_rows = 1
> string_fill_char =
> struct_levels_to_print = 2
> suppress_verbose_help_message = 0
> _______________________________________________
> Bug-octave mailing list
> Bug-octave at cae.wisc.edu
> https://www-old.cae.wisc.edu/mailman/listinfo/bug-octave
>
--
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz
More information about the Bug-octave
mailing list