Tcl Library Source Code

Check-in [b908e8c70e]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Moved all the new things (doc, code, tests) which were added to the __generated__ numtheory.* files over into the true source, numtheory.dtx. Updated the stitch file to generate the new files (primes.*). Regenerated the derived files. Only differences are whitespace and comments. Tests pass.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: b908e8c70e8509c662d10e82b4c7737f1be256bc4c1414953354001faf1be3ca
User & Date: andreask 2018-07-09 18:44:13.399
Context
2018-07-09
19:17
math::numtheory - <B,T> Bugfix in `primeFactors`. Handle case of the search loop for factors running over the end of the list of known primes. Added test cases. Version bumped to 1.1.1 check-in: f1ef76f20c user: andreask tags: trunk
18:44
Moved all the new things (doc, code, tests) which were added to the __generated__ numtheory.* files over into the true source, numtheory.dtx. Updated the stitch file to generate the new files (primes.*). Regenerated the derived files. Only differences are whitespace and comments. Tests pass. check-in: b908e8c70e user: andreask tags: trunk
17:14
docstrip - Moved manpage changes from generated file into the actual package sources. No version change check-in: 180c2ac3c8 user: andreask tags: trunk
Changes
Unified Diff Ignore Whitespace Patch
Changes to modules/math/numtheory.dtx.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
% 
% \iffalse
% 
%<*pkg>
%% Copyright (c) 2010 by Lars Hellstrom.  All rights reserved.
%% See the file "license.terms" for information on usage and redistribution
%% of this file, and for a DISCLAIMER OF ALL WARRANTIES.
%</pkg>
%<*driver>
\documentclass{tclldoc}
\usepackage{amsmath,amsfonts}
\usepackage{url}
\newcommand{\Tcl}{\Tcllogo}
\begin{document}
\DocInput{numtheory.dtx}



|



|







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
% 
% \iffalse
% 
%<*pkg_common>
%% Copyright (c) 2010 by Lars Hellstrom.  All rights reserved.
%% See the file "license.terms" for information on usage and redistribution
%% of this file, and for a DISCLAIMER OF ALL WARRANTIES.
%</pkg_common>
%<*driver>
\documentclass{tclldoc}
\usepackage{amsmath,amsfonts}
\usepackage{url}
\newcommand{\Tcl}{\Tcllogo}
\begin{document}
\DocInput{numtheory.dtx}
36
37
38
39
40
41
42
43
44
45
46
47



















48
49
50
51


52
53












54
55
56

57
58










59


60
61















62



63
64
65














66


67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
%<*pkg>
package require Tcl 8.5
% \end{tcl}
% \Tcl~8.4 is seriously broken with respect to arithmetic overflow, 
% so we require 8.5. There are (as yet) no explicit 8.5-isms in the 
% code, however.
% \begin{tcl}
package provide math::numtheory 1.0
namespace eval ::math::numtheory {
   namespace export isprime
}
%</pkg>



















% \end{tcl}
% \setnamespace{math::numtheory}
% 
% \Tcl lib has its own test file boilerplate.


% \begin{tcl}
%<*test>












source [file join\
  [file dirname [file dirname [file join [pwd] [info script]]]]\
  devtools testutilities.tcl]

testsNeedTcl     8.5
testsNeedTcltest 2










testing {useLocal numtheory.tcl math::numtheory}


%</test>
% \end{tcl}















% 



% And the same is true for the manpage.
% \begin{tcl}
%<*man>














[manpage_begin math::numtheory n 1.0]


[copyright "2010 Lars Hellstr\u00F6m\ 
  <Lars dot Hellstrom at residenset dot net>"]
[moddesc   {Tcl Math Library}]
[titledesc {Number Theory}]
[category  Mathematics]
[require Tcl [opt 8.5]]
[require math::numtheory [opt 1.0]]

[description]
[para]
This package is for collecting various number-theoretic operations, 
though at the moment it only provides that of testing whether an 
integer is a prime.

[list_begin definitions]
%</man>
% \end{tcl}
% 
% 
% \section{Primes}
% 
% The first (and so far only) operation provided is |isprime|, which 
% tests if an integer is a prime.
% \begin{tcl}
%<*man>
[call [cmd math::numtheory::isprime] [arg N] [
   opt "[arg option] [arg value] ..."
]]
  The [cmd isprime] command tests whether the integer [arg N] is a 







|




>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>




>
>

|
>
>
>
>
>
>
>
>
>
>
>
>



>

|
>
>
>
>
>
>
>
>
>
>
|
>
>
|

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
>
>



>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
>






|



|
<
|








|







36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
%<*pkg>
package require Tcl 8.5
% \end{tcl}
% \Tcl~8.4 is seriously broken with respect to arithmetic overflow, 
% so we require 8.5. There are (as yet) no explicit 8.5-isms in the 
% code, however.
% \begin{tcl}
package provide math::numtheory 1.1
namespace eval ::math::numtheory {
   namespace export isprime
}
%</pkg>
% \end{tcl}
% Additional procedures are placed into a separate file primes.tcl,
% sourced from the primary.
% \begin{tcl}
%<*pkg_primes>
# primes.tcl --
#     Provide additional procedures for the number theory package
#
namespace eval ::math::numtheory {
    variable primes {2 3 5 7 11 13 17}
    variable nextPrimeCandidate 19
    variable nextPrimeIncrement  1 ;# Examine numbers 6n+1 and 6n+5

    namespace export firstNprimes primesLowerThan primeFactors uniquePrimeFactors factors \
                     totient moebius legendre jacobi gcd lcm \
                     numberPrimesGauss numberPrimesLegendre numberPrimesLegendreModified
}

%</pkg_primes>
% \end{tcl}
% \setnamespace{math::numtheory}
% 
% \Tcl lib has its own test file boilerplate.
% We require tcltest 2.1 to allow the definition of a custom matcher
% comparing lists of integers
% \begin{tcl}
%<*test_primes>
# -*- tcl -*-
# primes.test --
#    Additional test cases for the ::math::numtheory package
#
# Note:
#    The tests assume tcltest 2.1, in order to compare
#    list of integer results

# -------------------------------------------------------------------------

%</test_primes>
%<*test_common>
source [file join\
  [file dirname [file dirname [file join [pwd] [info script]]]]\
  devtools testutilities.tcl]

testsNeedTcl     8.5
testsNeedTcltest 2.1

%</test_common>
%<*test_primes>
support {
    useLocal math.tcl math
}

%</test_primes>
%<*test_common>
testing {
    useLocal numtheory.tcl math::numtheory
}

%</test_common>
% \end{tcl}
% and a bit more for the additional tests. This is where tcltest 2.1
% is required
% \begin{tcl}
%<*test_primes>
proc matchLists { expected actual } {
   set match 1
   foreach a $actual e $expected {
      if { $a != $e } {
         set match 0
         break
      }
   }
   return $match
}
customMatch equalLists matchLists

%</test_primes>
% \end{tcl}
% 
% And the same is true for the manpage.
% \begin{tcl}
%<*man>
[comment {
    __Attention__ This document is a generated file.
    It is not the true source.
    The true source is

        numtheory.dtx

    To make changes edit the true source, and then use
    
        sak.tcl docstrip/regen modules/math

    to update all generated files.
}]
[vset VERSION 1.1]
[manpage_begin math::numtheory n [vset VERSION]]
[keywords {number theory}]
[keywords prime]
[copyright "2010 Lars Hellstr\u00F6m\ 
  <Lars dot Hellstrom at residenset dot net>"]
[moddesc   {Tcl Math Library}]
[titledesc {Number Theory}]
[category  Mathematics]
[require Tcl [opt 8.5]]
[require math::numtheory [opt [vset VERSION]]]

[description]
[para]
This package is for collecting various number-theoretic operations, with

a slight bias to prime numbers.

[list_begin definitions]
%</man>
% \end{tcl}
% 
% 
% \section{Primes}
% 
% The first operation provided is |isprime|, which 
% tests if an integer is a prime.
% \begin{tcl}
%<*man>
[call [cmd math::numtheory::isprime] [arg N] [
   opt "[arg option] [arg value] ..."
]]
  The [cmd isprime] command tests whether the integer [arg N] is a 
118
119
120
121
122
123
124



















































































































































































































125
126
127
128
129
130
131
    which controls how many times the Miller-Rabin test should be 
    repeated with randomly chosen bases. Each repetition reduces the 
    probability of a false positive by a factor at least 4. The 
    default for [arg repetitions] is 4.
  [list_end]
  Unknown options are silently ignored.




















































































































































































































%</man>
% \end{tcl}
% 
% 
% \subsection{Trial division}
% 
% As most books on primes will tell you, practical primality 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
    which controls how many times the Miller-Rabin test should be 
    repeated with randomly chosen bases. Each repetition reduces the 
    probability of a false positive by a factor at least 4. The 
    default for [arg repetitions] is 4.
  [list_end]
  Unknown options are silently ignored.

%</man>
% \end{tcl}
% Then we have |firstNprimes|, which returns a list containing
% the first |n| primes.
% \begin{tcl}
%<*man>
[call [cmd math::numtheory::firstNprimes] [arg N]]
Return the first N primes

[list_begin arguments]
[arg_def integer N in]
Number of primes to return
[list_end]

[call [cmd math::numtheory::primesLowerThan] [arg N]]
Return the prime numbers lower/equal to N

[list_begin arguments]
[arg_def integer N in]
Maximum number to consider
[list_end]

[call [cmd math::numtheory::primeFactors] [arg N]]
Return a list of the prime numbers in the number N

[list_begin arguments]
[arg_def integer N in]
Number to be factorised
[list_end]

%</man>
% \end{tcl}
% Similarly |primesLowerThan| returns a list of the prime numbers
% which are less than |n|, or equal to it.
% \begin{tcl}
%<*man>
[call [cmd math::numtheory::primesLowerThan] [arg N]]
Return the prime numbers lower/equal to N

[list_begin arguments]
[arg_def integer N in]
Maximum number to consider
[list_end]

%</man>
% \end{tcl}
% Then |primeFactors| returns the list of the prime numbers in |n|.
% \begin{tcl}
%<*man>
[call [cmd math::numtheory::primeFactors] [arg N]]
Return a list of the prime numbers in the number N

[list_begin arguments]
[arg_def integer N in]
Number to be factorised
[list_end]

%</man>
% \end{tcl}
% And |uniquePrimeFactors| does the same, with duplicates removed.
% \begin{tcl}
%<*man>
[call [cmd math::numtheory::uniquePrimeFactors] [arg N]]
Return a list of the [emph unique] prime numbers in the number N

[list_begin arguments]
[arg_def integer N in]
Number to be factorised
[list_end]

%</man>
% \end{tcl}
% |factors| returns all factors of |n|, not just just primes.
% \begin{tcl}
%<*man>
[call [cmd math::numtheory::factors] [arg N]]
Return a list of all [emph unique] factors in the number N, including 1 and N itself
[list_begin arguments]
[arg_def integer N in]
Number to be factorised
[list_end]

%</man>
% \end{tcl}
% |totient| computes the Euler totient for |n|
% \begin{tcl}
%<*man>
[call [cmd math::numtheory::totient] [arg N]]
Evaluate the Euler totient function for the number N (number of numbers
relatively prime to N)

[list_begin arguments]
[arg_def integer N in]
Number in question
[list_end]

%</man>
% \end{tcl}
% |moebius| computes the Moebious function on |n|.
% \begin{tcl}
%<*man>
[call [cmd math::numtheory::moebius] [arg N]]
Evaluate the Moebius function for the number N

[list_begin arguments]
[arg_def integer N in]
Number in question
[list_end]

%</man>
% \end{tcl}
% |legendre| computes the Legendre symbol (|a/p|).
% \begin{tcl}
%<*man>
[call [cmd math::numtheory::legendre] [arg a] [arg p]]
Evaluate the Legendre symbol (a/p)

[list_begin arguments]
[arg_def integer a in]
Upper number in the symbol
[arg_def integer p in]
Lower number in the symbol (must be non-zero)
[list_end]

%</man>
% \end{tcl}
% |jacobi| compute the Jacobi symbol (|a/p|).
% \begin{tcl}
%<*man>
[call [cmd math::numtheory::jacobi] [arg a] [arg b]]
Evaluate the Jacobi symbol (a/b)

[list_begin arguments]
[arg_def integer a in]
Upper number in the symbol
[arg_def integer b in]
Lower number in the symbol (must be odd)
[list_end]

%</man>
% \end{tcl}
% |gcd| computes the greatest common divisor of |n| and |m|.
% \begin{tcl}
%<*man>
[call [cmd math::numtheory::gcd] [arg m] [arg n]]
Return the greatest common divisor of [term m] and [term n]

[list_begin arguments]
[arg_def integer m in]
First number
[arg_def integer n in]
Second number
[list_end]

%</man>
% \end{tcl}
% |lcm| computes the least common multiple of |n| and |m|.
% \begin{tcl}
%<*man>
[call [cmd math::numtheory::lcm] [arg m] [arg n]]
Return the lowest common multiple of [term m] and [term n]

[list_begin arguments]
[arg_def integer m in]
First number
[arg_def integer n in]
Second number
[list_end]

%</man>
% \end{tcl}
% |numberPrimesGauss| estimates the number of primes below |n|
% using a formula by Gauss.
% \begin{tcl}
%<*man>
[call [cmd math::numtheory::numberPrimesGauss] [arg N]]
Estimate the number of primes according the formula by Gauss.

[list_begin arguments]
[arg_def integer N in]
Number in question
[list_end]

%</man>
% \end{tcl}
% |numberPrimesLegendre| estimates the number of primes below |n|
% using a formula by Legendre.
% \begin{tcl}
%<*man>
[call [cmd math::numtheory::numberPrimesLegendre] [arg N]]
Estimate the number of primes according the formula by Legendre.

[list_begin arguments]
[arg_def integer N in]
Number in question
[list_end]

%</man>
% \end{tcl}
% |numberPrimesLegendreModified| estimates the number of primes below
% |n| using Legendre's modified formula.
% \begin{tcl}
%<*man>
[call [cmd math::numtheory::numberPrimesLegendreModified] [arg N]]
Estimate the number of primes according the modified formula by Legendre.

[list_begin arguments]
[arg_def integer N in]
Number in question
[list_end]

%</man>
% \end{tcl}
% 
% 
% \subsection{Trial division}
% 
% As most books on primes will tell you, practical primality 
733
734
735
736
737
738
739




740
741
742
743
744
745
746
%   That ends the |for| loop for |Miller--Rabin| with random bases.
%   At this point, since the number in question passed the requested 
%   number of Miller--Rabin rounds, it is proclaimed to be ``probably 
%   prime''.
%   \begin{tcl}
    return on
}




%</pkg>
%   \end{tcl}
%   
%   Tests of |isprime| would mostly be asking ``is $n$ a prime'' for 
%   various interesting $n$. Several values of $n$ should be the same 
%   as the previous tests:
%   \begin{tcl}







>
>
>
>







1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
%   That ends the |for| loop for |Miller--Rabin| with random bases.
%   At this point, since the number in question passed the requested 
%   number of Miller--Rabin rounds, it is proclaimed to be ``probably 
%   prime''.
%   \begin{tcl}
    return on
}

# Add the additional procedures
#
source [file join [file dirname [info script]] primes.tcl]
%</pkg>
%   \end{tcl}
%   
%   Tests of |isprime| would mostly be asking ``is $n$ a prime'' for 
%   various interesting $n$. Several values of $n$ should be the same 
%   as the previous tests:
%   \begin{tcl}
874
875
876
877
878
879
880

























































































































































































































































































































































































































































































































































































881
882
883
884
885
886
887
888

889
890
891
892
893
894
895
896
897
898
899
900
901
      rename _orig_Miller--Rabin Miller--Rabin
   }
}
%</test>
%   \end{tcl}
% \end{proc}
% 

























































































































































































































































































































































































































































































































































































% 
% \section*{Closings}
% 
% \begin{tcl}
%<*man>
[list_end]

[keywords {number theory} prime]

[manpage_end]
%</man>
% \end{tcl}
% 
% \begin{tcl}
%<test>testsuiteCleanup
% \end{tcl}
% 
% 
% \begin{thebibliography}{9}
% 
% \bibitem{AKS04}
%   Manindra Agrawal, Neeraj Kayal, and Nitin Saxena:







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







|
>





|







1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
      rename _orig_Miller--Rabin Miller--Rabin
   }
}
%</test>
%   \end{tcl}
% \end{proc}
% 
% \section {Add-ons}
%
% A number of additional functions around factoring numbers
%
% \begin{tcl}
%<*pkg_primes>
# ComputeNextPrime --
#     Determine the next prime
#
# Arguments:
#     None
#
# Result:
#     None
#
# Side effects:
#     One prime added to the list of primes
#
# Note:
#     Using a true sieve of Erathostenes might be faster, but
#     this does work. Even computing the first ten thousand
#     does not seem to be slow.
#
proc ::math::numtheory::ComputeNextPrime {} {
    variable primes
    variable nextPrimeCandidate
    variable nextPrimeIncrement

    while {1} {
        #
        # Test the current candidate
        #
        set sqrtCandidate [expr {sqrt($nextPrimeCandidate)}]

        set isprime 1
        foreach p $primes {
            if { $p > $sqrtCandidate } {
                break
            }
            if { $nextPrimeCandidate % $p == 0 } {
                set isprime 0
                break
            }
        }

        if { $isprime } {
            lappend primes $nextPrimeCandidate
        }

        #
        # In any case get the next candidate
        #
        if { $nextPrimeIncrement == 1 } {
            set nextPrimeIncrement 5
            set nextPrimeCandidate [expr {$nextPrimeCandidate + 4}]
        } else {
            set nextPrimeIncrement 1
            set nextPrimeCandidate [expr {$nextPrimeCandidate + 2}]
        }

        if { $isprime } {
            break
        }
    }
}

# firstNprimes --
#     Return the first N primes
#
# Arguments:
#     number           Number of primes to return
#
# Result:
#     List of the first $number primes
#
proc ::math::numtheory::firstNprimes {number} {
    variable primes

    while { [llength $primes] < $number } {
        ComputeNextPrime
    }

    return [lrange $primes 0 [expr {$number-1}]]
}

# primesLowerThan --
#     Return the primes lower than some threshold
#
# Arguments:
#     threshold        Threshold for the primes
#
# Result:
#     List of primes lower/equal to the threshold
#
proc ::math::numtheory::primesLowerThan {threshold} {
    variable primes

    while { [lindex $primes end] < $threshold } {
        ComputeNextPrime
    }

    set n 0
    foreach p $primes {
        if { $p > $threshold } {
            break
        } else {
            incr n
        }
    }
    return [lrange $primes 0 [expr {$n-1}]]
}

# primeFactors --
#     Determine the prime factors of a number
#
# Arguments:
#     number           Number to factorise
#
# Result:
#     List of prime factors
#
proc ::math::numtheory::primeFactors {number} {
    variable primes

    #
    # Make sure we have enough primes
    #
    primesLowerThan [expr {sqrt($number)}]

    set factors {}

    set idx 0

    while { $number > 1 } {
        set p [lindex $primes $idx]
        if { $number % $p == 0 } {
            lappend factors $p
            set number [expr {$number/$p}]
        } else {
            incr idx
        }
    }

    return $factors
}

# uniquePrimeFactors --
#     Determine the unique prime factors of a number
#
# Arguments:
#     number           Number to factorise
#
# Result:
#     List of unique prime factors
#
proc ::math::numtheory::uniquePrimeFactors {number} {
    return [lsort -unique -integer [primeFactors $number]]
}

# totient --
#     Evaluate the Euler totient function for a number
#
# Arguments:
#     number           Number in question
#
# Result:
#     Totient of the given number (number of numbers
#     relatively prime to the number)
#
proc ::math::numtheory::totient {number} {
    set factors [uniquePrimeFactors $number]

    set totient 1

    foreach f $factors {
        set totient [expr {$totient * ($f-1)}]
    }

    return $totient
}

# factors --
#     Return all (unique) factors of a number
#
# Arguments:
#     number           Number in question
#
# Result:
#     List of factors including 1 and the number itself
#
# Note:
#     The algorithm for constructing the power set was taken from
#     wiki.tcl.tk/2877 (algorithm subsets2b).
#
proc ::math::numtheory::factors {number} {
    set factors [primeFactors $number]

    #
    # Iterate over the power set of this list
    #
    set result [list 1 $number]
    for {set n 1} {$n < [llength $factors]} {incr n} {
        set subsets [list [list]]
        foreach f $factors {
            foreach subset $subsets {
                lappend subset $f
                if {[llength $subset] == $n} {
                    lappend result [Product $subset]
                } else {
                    lappend subsets $subset
                }
            }
        }
    }
    return [lsort -unique -integer $result]
}

# Product --
#     Auxiliary function: return the product of a list of numbers
#
# Arguments:
#     list           List of numbers
#
# Result:
#     The product of all the numbers
#
proc ::math::numtheory::Product {list} {
    set product 1
    foreach e $list {
        set product [expr {$product * $e}]
    }
    return $product
}

# moebius --
#     Return the value of the Moebius function for "number"
#
# Arguments:
#     number         Number in question
#
# Result:
#     The product of all the numbers
#
proc ::math::numtheory::moebius {number} {
    if { $number < 1 } {
        return -code error "The number must be positive"
    }
    if { $number == 1 } {
        return 1
    }

    set primefactors [primeFactors $number]
    if { [llength $primefactors] != [llength [lsort -unique -integer $primefactors]] } {
        return 0
    } else {
        return [expr {(-1)**([llength $primefactors]%2)}]
    }
}

# legendre --
#     Return the value of the Legendre symbol (a/p)
#
# Arguments:
#     a              Upper number in the symbol
#     p              Lower number in the symbol
#
# Result:
#     The Legendre symbol
#
proc ::math::numtheory::legendre {a p} {
    if { $p == 0 } {
        return -code error "The number p must be non-zero"
    }

    if { $a % $p == 0 } {
        return 0
    }

    #
    # Just take the brute force route
    # (Negative values of a present a small problem, but only a small one)
    #
    while { $a < 0 } {
        set a [expr {$p + $a}]
    }

    set legendre -1
    for {set n 1} {$n < $p} {incr n} {
        if { $n**2 % $p == $a } {
            set legendre 1
            break
        }
    }

    return $legendre
}

# jacobi --
#     Return the value of the Jacobi symbol (a/b)
#
# Arguments:
#     a              Upper number in the symbol
#     b              Lower number in the symbol
#
# Result:
#     The Jacobi symbol
#
# Note:
#     Implementation adopted from the Wiki - http://wiki.tcl.tk/36990
#     encoded by rmelton 9/25/12
#     Further references:
#     http://en.wikipedia.org/wiki/Jacobi_symbol
#     http://2000clicks.com/mathhelp/NumberTh27JacobiSymbolAlgorithm.aspx
#
proc ::math::numtheory::jacobi {a b} {
    if { $b<=0 || ($b&1)==0 } {
        return 0;
    }

    set j 1
    if {$a<0} {
        set a [expr {0-$a}]
        set j [expr {0-$j}]
    }
    while {$a != 0} {
        while {($a&1) == 0} {
            ##/* Process factors of 2: Jacobi(2,b)=-1 if b=3,5 (mod 8) */
            set a [expr {$a>>1}]
            if {(($b & 7)==3) || (($b & 7)==5)} {
                set j [expr {0-$j}]
            }
        }
        ##/* Quadratic reciprocity: Jacobi(a,b)=-Jacobi(b,a) if a=3,b=3 (mod 4) */
        lassign [list $a $b] b a
        if {(($a & 3)==3) && (($b & 3)==3)} {
            set j [expr {0-$j}]
        }
        set a [expr {$a % $b}]
    }
    if {$b==1} {
        return $j
    } else {
        return 0
    }
}

# gcd --
#     Return the greatest common divisor of two numbers n and m
#
# Arguments:
#     n              First number
#     m              Second number
#
# Result:
#     The greatest common divisor
#
proc ::math::numtheory::gcd {n m} {
    #
    # Apply Euclid's good old algorithm
    #
    if { $n > $m } {
        set t $n
        set n $m
        set m $t
    }

    while { $n > 0 } {
        set r [expr {$m % $n}]
        set m $n
        set n $r
    }

    return $m
}

# lcm --
#     Return the lowest common multiple of two numbers n and m
#
# Arguments:
#     n              First number
#     m              Second number
#
# Result:
#     The lowest common multiple
#
proc ::math::numtheory::lcm {n m} {
    set gcd [gcd $n $m]
    return [expr {$n*$m/$gcd}]
}

# numberPrimesGauss --
#     Return the approximate number of primes lower than the given value based on the formula by Gauss
#
# Arguments:
#     limit            The limit for the largest prime to be included in the estimate
#
# Returns:
#     Approximate number of primes
#
proc ::math::numtheory::numberPrimesGauss {limit} {
    if { $limit <= 1 } {
        return -code error "The limit must be larger than 1"
    }
    expr {$limit / log($limit)}
}

# numberPrimesLegendre --
#     Return the approximate number of primes lower than the given value based on the formula by Legendre
#
# Arguments:
#     limit            The limit for the largest prime to be included in the estimate
#
# Returns:
#     Approximate number of primes
#
proc ::math::numtheory::numberPrimesLegendre {limit} {
    if { $limit <= 1 } {
        return -code error "The limit must be larger than 1"
    }
    expr {$limit / (log($limit) - 1.0)}
}

# numberPrimesLegendreModified --
#     Return the approximate number of primes lower than the given value based on the
#     modified formula by Legendre
#
# Arguments:
#     limit            The limit for the largest prime to be included in the estimate
#
# Returns:
#     Approximate number of primes
#
proc ::math::numtheory::numberPrimesLegendreModified {limit} {
    if { $limit <= 1 } {
        return -code error "The limit must be larger than 1"
    }
    expr {$limit / (log($limit) - 1.08366)}
}
%</pkg_primes>
%\end{tcl}
% \begin{tcl}
%<*test_primes>
test first-few-primes-1 "First 10 primes" -match equalLists -body {
    ::math::numtheory::firstNprimes 10
} -result {2 3 5 7 11 13 17 19 23 29}

test first-few-primes-2 "First 12 primes" -match equalLists -body {
    ::math::numtheory::firstNprimes 12
} -result {2 3 5 7 11 13 17 19 23 29 31 37}

test first-few-primes-3 "First 20 primes" -match equalLists -body {
    ::math::numtheory::firstNprimes 20
} -result {2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71}

test primes-lower-than-1 "Primes lower/equal 101" -match equalLists -body {
    ::math::numtheory::primesLowerThan 101
} -result {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}

test primes-lower-than-2 "Primes lower/equal 2" -match equalLists -body {
    ::math::numtheory::primesLowerThan 2
} -result {2}

test primes-lower-than-3 "Primes lower/equal 4" -match equalLists -body {
    ::math::numtheory::primesLowerThan 4
} -result {2 3}

test primes-lower-than-4 "Primes lower/equal 102" -match equalLists -body {
    ::math::numtheory::primesLowerThan 102
} -result {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}

test prime-factors-1 "Prime factors 100" -match equalLists -body {
    ::math::numtheory::primeFactors 100
} -result {2 2 5 5}

test prime-factors-2 "Unique prime factors 100" -match equalLists -body {
    ::math::numtheory::uniquePrimeFactors 100
} -result {2 5}

test prime-factors-3 "Prime factors 2900" -match equalLists -body {
    ::math::numtheory::primeFactors 2900
} -result {2 2 5 5 29}

test prime-factors-4 "Unique prime factors 2900" -match equalLists -body {
    ::math::numtheory::uniquePrimeFactors 2900
} -result {2 5 29}

test totient-1 "Totient 15" -body {
    ::math::numtheory::totient 15
} -result 8

test totient-2 "Totient 30" -body {
    ::math::numtheory::totient 30
} -result 8

test totient-3 "Totient 35" -body {
    ::math::numtheory::totient 35
} -result 24

test totient-4 "Totient 105" -body {
    ::math::numtheory::totient 105
} -result 48

test factors-1 "All factors 30" -match equalLists -body {
    ::math::numtheory::factors 30
} -result {1 2 3 5 6 10 15 30}

test factors-1 "All factors 128" -match equalLists -body {
    ::math::numtheory::factors 128
} -result {1 2 4 8 16 32 64 128}

test factors-1 "All factors 250" -match equalLists -body {
    ::math::numtheory::factors 250
} -result {1 2 5 10 25 50 125 250}

test moebius-1 "Moebius for first 19 numbers" -match equalLists -body {
    set result {}
    for {set n 1} {$n < 20} {incr n} {
        lappend result [::math::numtheory::moebius $n]
    }
    set result
} -result {1 -1 -1 0 -1 1 -1 0 0 1 -1 0 -1 1 1 0 -1 0 -1}

test legendre-1 "Legendre symbol (-1/3)" -body {
    ::math::numtheory::legendre -1 3
} -result -1
test legendre-2 "Legendre symbol (-3/7)" -body {
    ::math::numtheory::legendre -3 7
} -result 1

test jacobi-1 "Jacobi symbol (6/7)" -body {
    ::math::numtheory::jacobi 6 7
} -result -1

test jacobi-2 "Jacobi symbol (6/9)" -body {
    ::math::numtheory::jacobi 6 9
} -result 0

test jacobi-3 "Jacobi symbol (3/11)" -body {
    ::math::numtheory::jacobi 3 11
} -result 1

test gcd-1 "Greatest common divisor 2 and 3" -body {
    ::math::numtheory::gcd 2 3
} -result 1

test gcd-2 "Greatest common divisor 20 and 12" -body {
    ::math::numtheory::gcd 20 12
} -result 4

test gcd-3 "Greatest common divisor 600 and 125" -body {
    ::math::numtheory::gcd 600 125
} -result 25

test lcm-1 "Lowest common multiple 3 and 4" -body {
    ::math::numtheory::lcm 3 4
} -result 12

test lcm-2 "Lowest common multiple 12 and 20" -body {
    ::math::numtheory::lcm 12 20
} -result 60

test number-primes "Exercise prime estimators" -match equalLists -body {
    set estimate1 [::math::numtheory::numberPrimesGauss 1000]
    set estimate2 [::math::numtheory::numberPrimesLegendre 1000]
    set estimate3 [::math::numtheory::numberPrimesLegendreModified 1000]
    set result [list [expr {int($estimate1)}] [expr {int($estimate2)}] [expr {int($estimate3)}]]
} -result {144 169 171}
%</test_primes>
%\end{tcl}
% 
% \section*{Closings}
% 
% \begin{tcl}
%<*man>
[list_end]

[vset CATEGORY {math :: numtheory}]
[include ../doctools2base/include/feedback.inc]
[manpage_end]
%</man>
% \end{tcl}
% 
% \begin{tcl}
%<test_common>testsuiteCleanup
% \end{tcl}
% 
% 
% \begin{thebibliography}{9}
% 
% \bibitem{AKS04}
%   Manindra Agrawal, Neeraj Kayal, and Nitin Saxena:
Changes to modules/math/numtheory.man.














1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17














[manpage_begin math::numtheory n 1.0]
[keywords {number theory}]
[keywords prime]
[copyright "2010 Lars Hellstr\u00F6m\
  <Lars dot Hellstrom at residenset dot net>"]
[moddesc   {Tcl Math Library}]
[titledesc {Number Theory}]
[category  Mathematics]
[require Tcl [opt 8.5]]
[require math::numtheory [opt 1.0]]

[description]
[para]
This package is for collecting various number-theoretic operations, with
a slight bias to prime numbers.

[list_begin definitions]
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|








|







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
[comment {
    __Attention__ This document is a generated file.
    It is not the true source.
    The true source is

        numtheory.dtx

    To make changes edit the true source, and then use

        sak.tcl docstrip/regen modules/math

    to update all generated files.
}]
[vset VERSION 1.1]
[manpage_begin math::numtheory n [vset VERSION]]
[keywords {number theory}]
[keywords prime]
[copyright "2010 Lars Hellstr\u00F6m\
  <Lars dot Hellstrom at residenset dot net>"]
[moddesc   {Tcl Math Library}]
[titledesc {Number Theory}]
[category  Mathematics]
[require Tcl [opt 8.5]]
[require math::numtheory [opt [vset VERSION]]]

[description]
[para]
This package is for collecting various number-theoretic operations, with
a slight bias to prime numbers.

[list_begin definitions]
51
52
53
54
55
56
57
















58
59
60
61
62
63
64
[call [cmd math::numtheory::firstNprimes] [arg N]]
Return the first N primes

[list_begin arguments]
[arg_def integer N in]
Number of primes to return
[list_end]

















[call [cmd math::numtheory::primesLowerThan] [arg N]]
Return the prime numbers lower/equal to N

[list_begin arguments]
[arg_def integer N in]
Maximum number to consider







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
[call [cmd math::numtheory::firstNprimes] [arg N]]
Return the first N primes

[list_begin arguments]
[arg_def integer N in]
Number of primes to return
[list_end]

[call [cmd math::numtheory::primesLowerThan] [arg N]]
Return the prime numbers lower/equal to N

[list_begin arguments]
[arg_def integer N in]
Maximum number to consider
[list_end]

[call [cmd math::numtheory::primeFactors] [arg N]]
Return a list of the prime numbers in the number N

[list_begin arguments]
[arg_def integer N in]
Number to be factorised
[list_end]

[call [cmd math::numtheory::primesLowerThan] [arg N]]
Return the prime numbers lower/equal to N

[list_begin arguments]
[arg_def integer N in]
Maximum number to consider
Changes to modules/math/numtheory.stitch.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15



16
17




# -*- tcl -*-
# Stitch definition for docstrip files, used by SAK.

input numtheory.dtx

options -metaprefix \# -preamble {In other words:
**************************************
* This Source is not the True Source *
**************************************
the true source is the file from which this one was generated.
}

stitch numtheory.tcl       pkg
stitch numtheory.test      test




options -nopreamble -nopostamble
stitch numtheory.man      man
















|
|

>
>
>
|

>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- tcl -*-
# Stitch definition for docstrip files, used by SAK.

input numtheory.dtx

options -metaprefix \# -preamble {In other words:
**************************************
* This Source is not the True Source *
**************************************
the true source is the file from which this one was generated.
}

stitch numtheory.tcl       {pkg pkg_common}
stitch numtheory.test      {test test_common}

stitch primes.tcl          {pkg_primes pkg_common}
stitch primes.test         {test_primes test_common}

options -nopostamble -nopreamble
stitch numtheory.man      man

# Unused guards:
#
# - driver	(TeX output prolog)
Changes to modules/math/numtheory.tcl.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
##
## This is the file `numtheory.tcl',
## generated with the SAK utility
## (sak docstrip/regen).
##
## The original source files were:
##
## numtheory.dtx  (with options: `pkg')
##
## In other words:
## **************************************
## * This Source is not the True Source *
## **************************************
## the true source is the file from which this one was generated.
##
# Copyright (c) 2010 by Lars Hellstrom.  All rights reserved.
|



|

|
|
|







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
## 
## This is the file `numtheory.tcl',
## generated with the SAK utility
## (sak docstrip/regen).
## 
## The original source files were:
## 
## numtheory.dtx  (with options: `pkg pkg_common')
## 
## In other words:
## **************************************
## * This Source is not the True Source *
## **************************************
## the true source is the file from which this one was generated.
##
# Copyright (c) 2010 by Lars Hellstrom.  All rights reserved.
73
74
75
76
77
78
79
80
81
82
    }
    return on
}

# Add the additional procedures
#
source [file join [file dirname [info script]] primes.tcl]
##
##
## End of file `numtheory.tcl'.







|
|

73
74
75
76
77
78
79
80
81
82
    }
    return on
}

# Add the additional procedures
#
source [file join [file dirname [info script]] primes.tcl]
## 
## 
## End of file `numtheory.tcl'.
Changes to modules/math/numtheory.test.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

19
20


21


22
23
24
25
26
27
28
##
## This is the file `numtheory.test',
## generated with the SAK utility
## (sak docstrip/regen).
##
## The original source files were:
##
## numtheory.dtx  (with options: `test')
##
## In other words:
## **************************************
## * This Source is not the True Source *
## **************************************
## the true source is the file from which this one was generated.
##
source [file join\
  [file dirname [file dirname [file join [pwd] [info script]]]]\
  devtools testutilities.tcl]

testsNeedTcl     8.5
testsNeedTcltest 2


testing {useLocal numtheory.tcl math::numtheory}


test prime_trialdivision-1 "Trial division of 1" -body {
   ::math::numtheory::prime_trialdivision 1
} -returnCodes 2 -result 0
test prime_trialdivision-2 "Trial division of 2" -body {
   ::math::numtheory::prime_trialdivision 2
} -returnCodes 2 -result 1
test prime_trialdivision-3 "Trial division of 6" -body {
|



|

|
|
|









>

|
>
>
|
>
>







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
## 
## This is the file `numtheory.test',
## generated with the SAK utility
## (sak docstrip/regen).
## 
## The original source files were:
## 
## numtheory.dtx  (with options: `test test_common')
## 
## In other words:
## **************************************
## * This Source is not the True Source *
## **************************************
## the true source is the file from which this one was generated.
##
source [file join\
  [file dirname [file dirname [file join [pwd] [info script]]]]\
  devtools testutilities.tcl]

testsNeedTcl     8.5
testsNeedTcltest 2.1

testing {
    useLocal numtheory.tcl math::numtheory
}

test prime_trialdivision-1 "Trial division of 1" -body {
   ::math::numtheory::prime_trialdivision 1
} -returnCodes 2 -result 0
test prime_trialdivision-2 "Trial division of 2" -body {
   ::math::numtheory::prime_trialdivision 2
} -returnCodes 2 -result 1
test prime_trialdivision-3 "Trial division of 6" -body {
198
199
200
201
202
203
204
205
206
207
208
209
   ::math::numtheory::isprime 118670087467 -randommr 500
} -result on -cleanup {
   namespace eval ::math::numtheory {
      rename Miller--Rabin ""
      rename _orig_Miller--Rabin Miller--Rabin
   }
}

testsuiteCleanup
##
##
## End of file `numtheory.test'.







<

|
|

203
204
205
206
207
208
209

210
211
212
213
   ::math::numtheory::isprime 118670087467 -randommr 500
} -result on -cleanup {
   namespace eval ::math::numtheory {
      rename Miller--Rabin ""
      rename _orig_Miller--Rabin Miller--Rabin
   }
}

testsuiteCleanup
## 
## 
## End of file `numtheory.test'.
Changes to modules/math/primes.tcl.


















1
2
3
4
5
6
7


















# primes.tcl --
#     Provide additional procedures for the number theory package
#
namespace eval ::math::numtheory {
    variable primes {2 3 5 7 11 13 17}
    variable nextPrimeCandidate 19
    variable nextPrimeIncrement  1 ;# Examine numbers 6n+1 and 6n+5
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
## 
## This is the file `primes.tcl',
## generated with the SAK utility
## (sak docstrip/regen).
## 
## The original source files were:
## 
## numtheory.dtx  (with options: `pkg_primes pkg_common')
## 
## In other words:
## **************************************
## * This Source is not the True Source *
## **************************************
## the true source is the file from which this one was generated.
##
# Copyright (c) 2010 by Lars Hellstrom.  All rights reserved.
# See the file "license.terms" for information on usage and redistribution
# of this file, and for a DISCLAIMER OF ALL WARRANTIES.
# primes.tcl --
#     Provide additional procedures for the number theory package
#
namespace eval ::math::numtheory {
    variable primes {2 3 5 7 11 13 17}
    variable nextPrimeCandidate 19
    variable nextPrimeIncrement  1 ;# Examine numbers 6n+1 and 6n+5
439
440
441
442
443
444
445



#
proc ::math::numtheory::numberPrimesLegendreModified {limit} {
    if { $limit <= 1 } {
        return -code error "The limit must be larger than 1"
    }
    expr {$limit / (log($limit) - 1.08366)}
}










>
>
>
457
458
459
460
461
462
463
464
465
466
#
proc ::math::numtheory::numberPrimesLegendreModified {limit} {
    if { $limit <= 1 } {
        return -code error "The limit must be larger than 1"
    }
    expr {$limit / (log($limit) - 1.08366)}
}
## 
## 
## End of file `primes.tcl'.
Changes to modules/math/primes.test.















1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

21
22
23
24
25
26
27















# -*- tcl -*-
# primes.test --
#    Additional test cases for the ::math::numtheory package
#
# Note:
#    The tests assume tcltest 2.1, in order to compare
#    list of integer results

# -------------------------------------------------------------------------

source [file join \
        [file dirname [file dirname [file join [pwd] [info script]]]] \
        devtools testutilities.tcl]

testsNeedTcl     8.5
testsNeedTcltest 2.1

support {
    useLocal math.tcl math
}

testing {
    useLocal numtheory.tcl math::numtheory
}

proc matchLists { expected actual } {
   set match 1
   foreach a $actual e $expected {
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>










|
|
|







>







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
## 
## This is the file `primes.test',
## generated with the SAK utility
## (sak docstrip/regen).
## 
## The original source files were:
## 
## numtheory.dtx  (with options: `test_primes test_common')
## 
## In other words:
## **************************************
## * This Source is not the True Source *
## **************************************
## the true source is the file from which this one was generated.
##
# -*- tcl -*-
# primes.test --
#    Additional test cases for the ::math::numtheory package
#
# Note:
#    The tests assume tcltest 2.1, in order to compare
#    list of integer results

# -------------------------------------------------------------------------

source [file join\
  [file dirname [file dirname [file join [pwd] [info script]]]]\
  devtools testutilities.tcl]

testsNeedTcl     8.5
testsNeedTcltest 2.1

support {
    useLocal math.tcl math
}

testing {
    useLocal numtheory.tcl math::numtheory
}

proc matchLists { expected actual } {
   set match 1
   foreach a $actual e $expected {
155
156
157
158
159
160
161





test number-primes "Exercise prime estimators" -match equalLists -body {
    set estimate1 [::math::numtheory::numberPrimesGauss 1000]
    set estimate2 [::math::numtheory::numberPrimesLegendre 1000]
    set estimate3 [::math::numtheory::numberPrimesLegendreModified 1000]
    set result [list [expr {int($estimate1)}] [expr {int($estimate2)}] [expr {int($estimate3)}]]
} -result {144 169 171}











>
>
>
>
171
172
173
174
175
176
177
178
179
180
181

test number-primes "Exercise prime estimators" -match equalLists -body {
    set estimate1 [::math::numtheory::numberPrimesGauss 1000]
    set estimate2 [::math::numtheory::numberPrimesLegendre 1000]
    set estimate3 [::math::numtheory::numberPrimesLegendreModified 1000]
    set result [list [expr {int($estimate1)}] [expr {int($estimate2)}] [expr {int($estimate3)}]]
} -result {144 169 171}
testsuiteCleanup
## 
## 
## End of file `primes.test'.