472:
Since the set of real numbers can only be specified up to a finite precision, an algorithm that did not place limits on the size of its coefficients would always find an integer relation for sufficiently large coefficients. Results of interest occur when the size of the coefficients in an integer
179:
for finding integer relations. Specifically, given a set of real numbers known to a given precision, an integer relation algorithm will either find an integer relation between them, or will determine that no integer relation exists with coefficients whose magnitudes are less than a certain
394:
for the original series, product or integral. This conjecture can then be validated by formal algebraic methods. The higher the precision to which the inputs to the algorithm are known, the greater the level of confidence that any integer relation that is found is not just a
389:
to a high degree of precision (usually at least 100 significant figures), and then use an integer relation algorithm to search for an integer relation between this value and a set of mathematical constants. If an integer relation is found, this suggests a possible
442: â 2) is a root of a 120th-degree polynomial whose largest coefficient is 257. Integer relation algorithms are combined with tables of high precision mathematical constants and heuristic search methods in applications such as the
1313:
253:
166:
741:
I. S. Kotsireas, and K. Karamanos, "Exact
Computation of the bifurcation Point B4 of the logistic Map and the BaileyâBroadhurst Conjectures", I. J. Bifurcation and Chaos 14(7):2417â2423 (2004)
1317:
825:
248:, it is not clear if the paper fully solves the problem because it lacks the detailed steps, proofs, and a precision bound that are crucial for a reliable implementation.
306:
in 1992 and substantially simplified by
Ferguson, Bailey, and Arno in 1999. In 2000 the PSLQ algorithm was selected as one of the "Top Ten Algorithms of the Century" by
858:
1182:
818:
766:
403:
1050:
1373:
992:
811:
921:
1098:
896:
786:
75:
1007:
1045:
982:
926:
889:
654:
1187:
1078:
997:
987:
772:
303:
863:
725:
1015:
633:
374:
313:
The LLL algorithm has been improved by numerous authors. Modern LLL implementations can solve integer relation problems with
232:; if there is an integer relation between the numbers, then their ratio is rational and the algorithm eventually terminates.
1268:
326:
Integer relation algorithms have numerous applications. The first application is to determine whether a given real number
1263:
1192:
1093:
1230:
454:
1144:
443:
1299:
1258:
1034:
1028:
1002:
873:
402:
A notable success of this approach was the use of the PSLQ algorithm to find the integer relation that led to the
1294:
1235:
710:
Helaman R. P. Ferguson, David H. Bailey and Steve Arno, ANALYSIS OF PSLQ, AN INTEGER RELATION FINDING ALGORITHM:
1197:
1070:
916:
868:
366:
1212:
1103:
447:
1323:
1273:
1253:
413:
391:
266:
974:
949:
878:
1333:
1328:
1220:
1202:
1177:
1139:
883:
417:
378:
1338:
1304:
1225:
1129:
1088:
1083:
1060:
964:
197:
241:
1169:
1116:
1113:
954:
853:
650:
215:
910:
903:
693:
1289:
1245:
959:
936:
798:
605:
580:
534:
509:
484:
640:
by
Helaman R. P. Ferguson and David H. Bailey; RNR Technical Report RNR-91-032; July 14, 1992
1134:
794:
382:
370:
331:
285:
281:
237:
1124:
1023:
790:
729:
711:
637:
262:
781:
277:
1154:
1055:
1040:
944:
845:
732:
Mathematics of
Computation, vol. 70, no. 236 (October 2000), pp. 1719â1736; LBNL-44481.
396:
473:
relation is small compared to the precision with which the real numbers are specified.
1367:
1149:
834:
776:
487:
350:}. The second application is to search for an integer relation between a real number
307:
258:
669:
1159:
722:
608:
583:
537:
421:
628:
512:
428:
is the logistic map's fourth bifurcation point, the constant α = â
310:
and
Francis Sullivan even though it is considered essentially equivalent to HJLS.
181:
803:
837:
613:
588:
559:
Polynomial time algorithms for finding integer relations among real numbers.
542:
517:
492:
176:
386:
699:
200:
can find any integer relation that exists between any two real numbers
723:"Parallel Integer Relation Detection: Techniques and Applications,"
557:
Johan HĂ„stad, Bettina Just, Jeffrey
Lagarias, Claus-Peter Schnorr:
334:, by searching for an integer relation between a set of powers of
630:
A Polynomial Time, Numerically Stable
Integer Relation Algorithm
807:
695:
A New View on HJLS and PSLQ: Sums and
Projections of Lattices.
655:"The Best of the 20th Century: Editors Name Top 10 Algorithms"
161:{\displaystyle a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}=0.\,}
407:
565:) Lecture Notes Computer Science 210 (1986), p. 105â118.
236:
The
FergusonâForcade algorithm was published in 1979 by
1354:
indicate that algorithm is for numbers of special forms
412:. PSLQ has also helped find new identities involving
78:
358:, Ï and ln(2), which will lead to an expression for
1282:
1244:
1211:
1168:
1112:
1069:
973:
935:
844:
214:. The algorithm generates successive terms of the
160:
251:The first algorithm with complete proofs was the
752:Factoring polynomials and the knapsack problem.
420:; and in identifying bifurcation points of the
819:
692:Jingwei Chen, Damien Stehlé, Gilles Villard:
8:
362:as a linear combination of these constants.
354:and a set of mathematical constants such as
563:Symposium Theoret. Aspects Computer Science
826:
812:
804:
754:J. of Number Theory, 95, 167â189, (2002).
721:David H. Bailey and David J. Broadhurst,
157:
145:
135:
116:
106:
93:
83:
77:
783:Ten Problems in Experimental Mathematics
453:Integer relation finding can be used to
465:
7:
377:to find an approximate value for an
244:. Although the paper treats general
14:
1035:Special number field sieve (SNFS)
1029:General number field sieve (GNFS)
561:Preliminary version: STACS 1986 (
295:, developed by Ferguson in 1988.
768:Recognizing Numerical Constants
404:BaileyâBorweinâPlouffe formula
375:arbitrary precision arithmetic
23:between a set of real numbers
1:
569:, Vol. 18 (1989), pp. 859â881
993:Lenstra elliptic curve (ECM)
302:, developed by Ferguson and
1374:Number theoretic algorithms
444:Inverse Symbolic Calculator
1390:
1300:Exponentiation by squaring
983:Continued fraction (CFRAC)
173:integer relation algorithm
1347:
196:= 2, an extension of the
416:and their appearance in
367:experimental mathematics
1213:Greatest common divisor
424:. For example, where B
414:multiple zeta functions
69:, not all 0, such that
1324:Modular exponentiation
797:, Vishaal Kapoor, and
392:closed-form expression
365:A typical approach in
162:
46:and a set of integers
16:Mathematical procedure
1051:Shanks's square forms
975:Integer factorization
950:Sieve of Eratosthenes
163:
1329:Montgomery reduction
1203:Function field sieve
1178:Baby-step giant-step
1024:Quadratic sieve (QS)
793:by David H. Bailey,
418:quantum field theory
76:
1339:Trachtenberg system
1305:Integer square root
1246:Modular square root
965:Wheel factorization
917:Quadratic Frobenius
897:LucasâLehmerâRiesel
795:Jonathan M. Borwein
668:(4). Archived from
651:Cipra, Barry Arthur
286:Claus-Peter Schnorr
198:Euclidean algorithm
1231:Extended Euclidean
1170:Discrete logarithm
1099:SchönhageâStrassen
955:Sieve of Pritchard
789:2011-06-10 at the
728:2011-07-20 at the
636:2007-07-17 at the
606:Weisstein, Eric W.
581:Weisstein, Eric W.
535:Weisstein, Eric W.
510:Weisstein, Eric W.
488:"Integer Relation"
485:Weisstein, Eric W.
455:factor polynomials
448:Plouffe's Inverter
397:numerical artifact
216:continued fraction
158:
1361:
1360:
960:Sieve of Sundaram
799:Eric W. Weisstein
406:for the value of
371:numerical methods
1381:
1310:Integer relation
1283:Other algorithms
1188:Pollard kangaroo
1079:Ancient Egyptian
937:Prime-generating
922:SolovayâStrassen
835:Number-theoretic
828:
821:
814:
805:
755:
748:
742:
739:
733:
719:
713:
708:
702:
690:
684:
683:
681:
680:
674:
659:
647:
641:
626:
620:
619:
618:
609:"PSLQ Algorithm"
601:
595:
594:
593:
584:"PSOS Algorithm"
576:
570:
555:
549:
548:
547:
538:"HJLS Algorithm"
530:
524:
523:
522:
505:
499:
498:
497:
480:
474:
470:
457:of high degree.
410:
383:infinite product
330:is likely to be
282:Jeffrey Lagarias
280:, Bettina Just,
238:Helaman Ferguson
167:
165:
164:
159:
150:
149:
140:
139:
121:
120:
111:
110:
98:
97:
88:
87:
21:integer relation
1389:
1388:
1384:
1383:
1382:
1380:
1379:
1378:
1364:
1363:
1362:
1357:
1343:
1278:
1240:
1207:
1164:
1108:
1065:
969:
931:
904:Proth's theorem
846:Primality tests
840:
832:
791:Wayback Machine
773:David H. Bailey
763:
758:
749:
745:
740:
736:
730:Wayback Machine
720:
716:
709:
705:
691:
687:
678:
676:
672:
657:
649:
648:
644:
638:Wayback Machine
627:
623:
604:
603:
602:
598:
579:
578:
577:
573:
567:SIAM J. Comput.
556:
552:
533:
532:
531:
527:
513:"LLL Algorithm"
508:
507:
506:
502:
483:
482:
481:
477:
471:
467:
463:
441:
434:
427:
408:
379:infinite series
324:
276:, developed by
263:Hendrik Lenstra
257:, developed by
231:
224:
213:
206:
190:
141:
131:
112:
102:
89:
79:
74:
73:
68:
59:
52:
45:
36:
29:
17:
12:
11:
5:
1387:
1385:
1377:
1376:
1366:
1365:
1359:
1358:
1356:
1355:
1348:
1345:
1344:
1342:
1341:
1336:
1331:
1326:
1321:
1307:
1302:
1297:
1292:
1286:
1284:
1280:
1279:
1277:
1276:
1271:
1266:
1264:TonelliâShanks
1261:
1256:
1250:
1248:
1242:
1241:
1239:
1238:
1233:
1228:
1223:
1217:
1215:
1209:
1208:
1206:
1205:
1200:
1198:Index calculus
1195:
1193:PohligâHellman
1190:
1185:
1180:
1174:
1172:
1166:
1165:
1163:
1162:
1157:
1152:
1147:
1145:Newton-Raphson
1142:
1137:
1132:
1127:
1121:
1119:
1110:
1109:
1107:
1106:
1101:
1096:
1091:
1086:
1081:
1075:
1073:
1071:Multiplication
1067:
1066:
1064:
1063:
1058:
1056:Trial division
1053:
1048:
1043:
1041:Rational sieve
1038:
1031:
1026:
1021:
1013:
1005:
1000:
995:
990:
985:
979:
977:
971:
970:
968:
967:
962:
957:
952:
947:
945:Sieve of Atkin
941:
939:
933:
932:
930:
929:
924:
919:
914:
907:
900:
893:
886:
881:
876:
871:
869:Elliptic curve
866:
861:
856:
850:
848:
842:
841:
833:
831:
830:
823:
816:
808:
802:
801:
779:
762:
761:External links
759:
757:
756:
750:M. van Hoeij:
743:
734:
714:
703:
685:
642:
621:
596:
571:
550:
525:
500:
475:
464:
462:
459:
439:
432:
425:
323:
320:
319:
318:
311:
300:PSLQ algorithm
296:
293:PSOS algorithm
289:
274:HJLS algorithm
270:
249:
229:
222:
211:
204:
189:
186:
169:
168:
156:
153:
148:
144:
138:
134:
130:
127:
124:
119:
115:
109:
105:
101:
96:
92:
86:
82:
64:
57:
50:
41:
34:
27:
15:
13:
10:
9:
6:
4:
3:
2:
1386:
1375:
1372:
1371:
1369:
1353:
1350:
1349:
1346:
1340:
1337:
1335:
1332:
1330:
1327:
1325:
1322:
1319:
1315:
1311:
1308:
1306:
1303:
1301:
1298:
1296:
1293:
1291:
1288:
1287:
1285:
1281:
1275:
1272:
1270:
1267:
1265:
1262:
1260:
1259:Pocklington's
1257:
1255:
1252:
1251:
1249:
1247:
1243:
1237:
1234:
1232:
1229:
1227:
1224:
1222:
1219:
1218:
1216:
1214:
1210:
1204:
1201:
1199:
1196:
1194:
1191:
1189:
1186:
1184:
1181:
1179:
1176:
1175:
1173:
1171:
1167:
1161:
1158:
1156:
1153:
1151:
1148:
1146:
1143:
1141:
1138:
1136:
1133:
1131:
1128:
1126:
1123:
1122:
1120:
1118:
1115:
1111:
1105:
1102:
1100:
1097:
1095:
1092:
1090:
1087:
1085:
1082:
1080:
1077:
1076:
1074:
1072:
1068:
1062:
1059:
1057:
1054:
1052:
1049:
1047:
1044:
1042:
1039:
1037:
1036:
1032:
1030:
1027:
1025:
1022:
1020:
1018:
1014:
1012:
1010:
1006:
1004:
1003:Pollard's rho
1001:
999:
996:
994:
991:
989:
986:
984:
981:
980:
978:
976:
972:
966:
963:
961:
958:
956:
953:
951:
948:
946:
943:
942:
940:
938:
934:
928:
925:
923:
920:
918:
915:
913:
912:
908:
906:
905:
901:
899:
898:
894:
892:
891:
887:
885:
882:
880:
877:
875:
872:
870:
867:
865:
862:
860:
857:
855:
852:
851:
849:
847:
843:
839:
836:
829:
824:
822:
817:
815:
810:
809:
806:
800:
796:
792:
788:
785:
784:
780:
778:
777:Simon Plouffe
774:
770:
769:
765:
764:
760:
753:
747:
744:
738:
735:
731:
727:
724:
718:
715:
712:
707:
704:
701:
697:
696:
689:
686:
675:on 2021-04-24
671:
667:
663:
656:
652:
646:
643:
639:
635:
632:
631:
625:
622:
616:
615:
610:
607:
600:
597:
591:
590:
585:
582:
575:
572:
568:
564:
560:
554:
551:
545:
544:
539:
536:
529:
526:
520:
519:
514:
511:
504:
501:
495:
494:
489:
486:
479:
476:
469:
466:
460:
458:
456:
451:
449:
445:
438:
431:
423:
419:
415:
411:
405:
400:
398:
393:
388:
384:
380:
376:
372:
368:
363:
361:
357:
353:
349:
345:
341:
337:
333:
329:
321:
316:
312:
309:
308:Jack Dongarra
305:
301:
297:
294:
290:
287:
283:
279:
275:
271:
268:
267:LĂĄszlĂł LovĂĄsz
264:
260:
259:Arjen Lenstra
256:
255:
254:LLL algorithm
250:
247:
243:
239:
235:
234:
233:
228:
221:
218:expansion of
217:
210:
203:
199:
195:
192:For the case
187:
185:
183:
178:
174:
154:
151:
146:
142:
136:
132:
128:
125:
122:
117:
113:
107:
103:
99:
94:
90:
84:
80:
72:
71:
70:
67:
63:
56:
49:
44:
40:
33:
26:
22:
1351:
1309:
1033:
1016:
1008:
927:MillerâRabin
909:
902:
895:
890:LucasâLehmer
888:
782:
767:
751:
746:
737:
717:
706:
694:
688:
677:. Retrieved
670:the original
665:
661:
645:
629:
624:
612:
599:
587:
574:
566:
562:
558:
553:
541:
528:
516:
503:
491:
478:
468:
452:
436:
429:
422:logistic map
401:
364:
359:
355:
351:
347:
343:
339:
335:
327:
325:
322:Applications
314:
299:
292:
278:Johan HĂ„stad
273:
252:
245:
242:R.W. Forcade
226:
219:
208:
201:
193:
191:
172:
170:
65:
61:
54:
47:
42:
38:
31:
24:
20:
18:
1183:Pollard rho
1140:Goldschmidt
874:Pocklington
864:BaillieâPSW
182:upper bound
1295:Cornacchia
1290:Chakravala
838:algorithms
679:2012-08-17
461:References
369:is to use
317:above 500.
1269:Berlekamp
1226:Euclidean
1114:Euclidean
1094:ToomâCook
1089:Karatsuba
662:SIAM News
614:MathWorld
589:MathWorld
543:MathWorld
518:MathWorld
493:MathWorld
332:algebraic
177:algorithm
126:⋯
1368:Category
1236:Lehmer's
1130:Chunking
1117:division
1046:Fermat's
787:Archived
726:Archived
700:ISSAC'13
634:Archived
387:integral
288:in 1986.
269:in 1982.
1352:Italics
1274:Kunerth
1254:Cipolla
1135:Fourier
1104:FĂŒrer's
998:Euler's
988:Dixon's
911:PĂ©pin's
346:, ...,
188:History
60:, ...,
37:, ...,
1334:Schoof
1221:Binary
1125:Binary
1061:Shor's
879:Fermat
385:or an
304:Bailey
284:, and
175:is an
1155:Short
884:Lucas
673:(PDF)
658:(PDF)
1150:Long
1084:Long
775:and
373:and
338:{1,
298:The
291:The
272:The
265:and
240:and
207:and
1314:LLL
1160:SRT
1019:+ 1
1011:â 1
859:APR
854:AKS
771:by
446:or
171:An
19:An
1370::
1318:KZ
1316:;
698:,
666:33
664:.
660:.
653:.
611:.
586:.
540:.
515:.
490:.
450:.
399:.
381:,
342:,
261:,
184:.
155:0.
53:,
30:,
1320:)
1312:(
1017:p
1009:p
827:e
820:t
813:v
682:.
617:.
592:.
546:.
521:.
496:.
440:4
437:B
435:(
433:4
430:B
426:4
409:Ï
360:x
356:e
352:x
348:x
344:x
340:x
336:x
328:x
315:n
246:n
230:2
227:x
225:/
223:1
220:x
212:2
209:x
205:1
202:x
194:n
152:=
147:n
143:x
137:n
133:a
129:+
123:+
118:2
114:x
108:2
104:a
100:+
95:1
91:x
85:1
81:a
66:n
62:a
58:2
55:a
51:1
48:a
43:n
39:x
35:2
32:x
28:1
25:x
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.