UNPKG

1.38 kBtext/coffeescriptView Raw
1# factor a polynomial or integer
2
3
4
5Eval_factor = ->
6 push(cadr(p1))
7 Eval()
8
9 push(caddr(p1))
10 Eval()
11
12 p2 = pop()
13 if (p2 == symbol(NIL))
14 guess()
15 else
16 push(p2)
17
18 factor()
19
20 # more factoring?
21
22 p1 = cdddr(p1)
23 while (iscons(p1))
24 push(car(p1))
25 Eval()
26 factor_again()
27 p1 = cdr(p1)
28
29factor_again = ->
30
31 save()
32
33 p2 = pop()
34 p1 = pop()
35
36 h = tos
37
38 if (car(p1) == symbol(MULTIPLY))
39 p1 = cdr(p1)
40 while (iscons(p1))
41 push(car(p1))
42 push(p2)
43 factor_term()
44 p1 = cdr(p1)
45 else
46 push(p1)
47 push(p2)
48 factor_term()
49
50 n = tos - h
51
52 if (n > 1)
53 multiply_all_noexpand(n)
54
55 restore()
56
57factor_term = ->
58 save()
59 factorpoly()
60 p1 = pop()
61 if (car(p1) == symbol(MULTIPLY))
62 p1 = cdr(p1)
63 while (iscons(p1))
64 push(car(p1))
65 p1 = cdr(p1)
66 else
67 push(p1)
68 restore()
69
70factor = ->
71 save()
72 p2 = pop()
73 p1 = pop()
74 if (isinteger(p1))
75 push(p1)
76 factor_number(); # see pollard.cpp
77 else
78 push(p1)
79 push(p2)
80 factorpoly()
81 restore()
82
83# for factoring small integers (2^32 or less)
84
85factor_small_number = ->
86
87 i = 0
88 save()
89
90 n = pop_integer()
91
92 if (isNaN(n))
93 stop("number too big to factor")
94
95 if (n < 0)
96 n = -n
97
98 for i in [0...MAXPRIMETAB]
99
100 d = primetab[i]
101
102 if (d > n / d)
103 break
104
105 expo = 0
106
107 while (n % d == 0)
108 n /= d
109 expo++
110
111 if (expo)
112 push_integer(d)
113 push_integer(expo)
114
115 if (n > 1)
116 push_integer(n)
117 push_integer(1)
118
119 restore()
120
121