Sharedwww / onhand / Factor / main.cOpen in CoCalc
Author: William A. Stein
1
/***********************************/
2
/* */
3
/* Factorization of integers */
4
/* uses the onHand/RuputerAPI */
5
/* */
6
/* William A. Stein, 6:23pm */
7
/* */
8
/***********************************/
9
10
/*
11
When you compile, an executable named factor.exf will be generated.
12
Then, after uploading it and starting, the softkeyboard will appear
13
in numerical input mode. Enter a number, and then its factorization
14
will appear.
15
16
===============================================================================
17
Copyright (c) 2000. William Stein
18
19
This is free open-source software. Enjoy!
20
===============================================================================
21
*/
22
23
24
#include <stdio.h>
25
#include <string.h>
26
27
#include "softkey.h"
28
#include "psdos.h"
29
#include "lcdbios.h"
30
#include "wbios.h"
31
#include "rupsys.h"
32
#include "font.h"
33
34
35
typedef unsigned long integer;
36
#define MAX_PRIME_DIVISORS 64
37
38
static const RECT CLRLCD={0,0,101,63};
39
40
void factor(integer N, integer *primes, integer *exponents);
41
integer get_input();
42
void display_answer(integer N, integer *primes, integer *exponents);
43
44
45
/*-----------------------------------------------------------*/
46
/* Main */
47
/*-----------------------------------------------------------*/
48
49
int main(void)
50
{
51
integer N;
52
integer primes[MAX_PRIME_DIVISORS],
53
exponents[MAX_PRIME_DIVISORS];
54
55
screen(1); /* Graphic mode */
56
gv_place(0,0); /* XY coordinates X:0, Y:0 */
57
endWaiting(); /* Stop startup animation. */
58
59
N = get_input();
60
if (N <= 0)
61
dos_exit(0);
62
primes[0]=0; /* initial to length 0 */
63
gv_kput(3,10,"Factoring...",5,0,0);
64
factor(N,primes,exponents); /* recursive trial division algorithm */
65
display_answer(N,primes,exponents);
66
}
67
68
69
/******************** SYSTEM I/O ****************/
70
71
#define Key_enter 0x0008
72
#define Key_menu 0x0002
73
74
void display_text(char* s0, char* s1, char* s2)
75
{
76
char* Mess[3];
77
Mess[0] = s0;
78
Mess[1] = s1;
79
Mess[2] = s2;
80
81
pv_clear((RECT *)&CLRLCD); /* Clear screen. */
82
if (dispMess((char**) Mess, 3 ) == -1)
83
dos_exit(0);
84
}
85
86
/* the library function that's supposed to do this doesn't work!! */
87
88
integer str_to_integer(char* str)
89
{
90
integer N = 0;
91
integer t = 1;
92
int i;
93
94
if (strlen(str) > 9) {
95
display_text("The maximum","number of digits", "is 9.");
96
return 0;
97
}
98
99
for (i = strlen(str)-1; i>=0; i--) {
100
if (str[i] < '0' || str[i] > '9') {
101
display_text("The input", str, "is not valid.");
102
return 0;
103
}
104
N += t * ((int)(str[i]-'0'));
105
t = t * 10;
106
}
107
108
return N;
109
}
110
111
integer get_input(void)
112
{
113
integer N;
114
char s[64];
115
116
char str[32];
117
int i;
118
119
KANJI_PUT Inputstr = {{0,32},str,5,0,0};
120
STRSTS ctrl = { picNAME , 5, 2,2,0,0,0,31};
121
122
for (i=0; i<32; i++)
123
str[i]='\0';
124
125
if (softkey(&ctrl,Inputstr.str,0,0) == -1)
126
dos_exit(0);
127
128
return str_to_integer(Inputstr.str);
129
}
130
131
132
133
void display_answer(integer N, integer *primes, integer *exponents)
134
{
135
char buf[64], num[64];
136
char* s;
137
int i;
138
int bt;
139
140
buf[0] = '\0';
141
s = buf;
142
143
for (i=0; i<MAX_PRIME_DIVISORS; i++) {
144
if (primes[i] == 0) break;
145
if (i>0)
146
sprintf(s, "*");
147
s += strlen(s);
148
sprintf(s,"%lu", primes[i]);
149
s += strlen(s);
150
if (exponents[i] > 1) {
151
sprintf(s,"^%lu", exponents[i]);
152
s += strlen(s);
153
}
154
}
155
156
sprintf(num, "%lu", N);
157
display_text(num, "=", buf);
158
}
159
160
161
/******************* MATHS *******************/
162
163
/* The algorithm is trial division, which should be fine.
164
Our integers are of type "int", so they are quite tiny. */
165
166
integer split(integer N)
167
{
168
static integer dif[] = {6, 4, 2, 4, 2, 4, 6, 2};
169
integer m;
170
integer ONE = 1, TWO = 2, THREE = 3, FIVE = 5;
171
172
int i;
173
174
if (N==ONE) {
175
return ONE;
176
} else if (N % TWO == 0) {
177
return TWO;
178
} else if (N % THREE == 0) {
179
return THREE;
180
} else if (N % FIVE == 0) {
181
return FIVE;
182
}
183
184
185
for (m=7, i=1; m*m <= N;) {
186
if (N % m == 0)
187
return m;
188
m += dif[(i++)%8 ];
189
}
190
191
return N;
192
}
193
194
void factor(integer N, integer *primes, integer *exponents)
195
{
196
int i, j;
197
integer n, m;
198
char buf0[64], buf1[64], buf2[64];
199
200
integer primes_m[MAX_PRIME_DIVISORS],
201
exponents_m[MAX_PRIME_DIVISORS];
202
primes_m[0];
203
204
n = split(N);
205
m = N / n;
206
207
if (m == 1) { /* N is prime */
208
primes[0] = n;
209
exponents[0] = 1;
210
primes[1] = 0;
211
return;
212
}
213
214
factor(n, primes, exponents);
215
factor(m, primes_m, exponents_m);
216
217
/* combine together the results */
218
for (i=0; i<MAX_PRIME_DIVISORS; i++) {
219
if (primes_m[i] == 0) break;
220
for (j=0; j<MAX_PRIME_DIVISORS; j++) {
221
if (primes[j] == 0) {
222
primes[j] = primes_m[i];
223
exponents[j]= exponents_m[i];
224
primes[j+1] = 0;
225
break;
226
} else if (primes[j] == primes_m[i]) {
227
exponents[j] += exponents_m[i];
228
break;
229
}
230
}
231
}
232
return;
233
}
234
235
236