Mercurial > ~darius > hgwebdir.cgi > paradise_server

comparison src/imath.c @ 4:aa38447a4b21

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
First entry of Paradise Server 2.9 patch 10 Beta
author darius
date Sat, 06 Dec 1997 04:37:03 +0000
parents
children
comparison
equal deleted inserted replaced
3:cafa94d86546 4:aa38447a4b21
1 /*--------------------------------------------------------------------------
2 NETREK II -- Paradise
3
4 Permission to use, copy, modify, and distribute this software and its
5 documentation, or any derivative works thereof, for any NON-COMMERCIAL
6 purpose and without fee is hereby granted, provided that this copyright
7 notice appear in all copies. No representations are made about the
8 suitability of this software for any purpose. This software is provided
9 "as is" without express or implied warranty.
10
11 Xtrek Copyright 1986 Chris Guthrie
12 Netrek (Xtrek II) Copyright 1989 Kevin P. Smith
13 Scott Silvey
14 Paradise II (Netrek II) Copyright 1993 Larry Denys
15 Kurt Olsen
16 Brandon Gillespie
17 --------------------------------------------------------------------------*/
18
19 /* collection of integer math routines. [BDyess] */
20
21 /*
22 * Based on (n+1)^2 = n^2 + 2n + 1 given that 1^2 = 1, then 2^2 = 1 + (2 +
23 * 1) = 1 + 3 = 4 3^2 = 4 + (4 + 1) = 4 + 5 = 1 + 3 + 5 = 9 4^2 = 9 + (6 + 1)
24 * = 9 + 7 = 1 + 3 + 5 + 7 = 16 ... In other words, a square number can be
25 * express as the sum of the series n^2 = 1 + 3 + ... + (2n-1)
26 *
27 * Note that NO multiplication or floating point math is needed. [BDyess]
28 */
29 int
30 isqrt(n)
31 int n;
32 {
33 int result = 0, sum = 1, prev = 1;
34
35 while (sum <= n)
36 {
37 prev += 2;
38 sum += prev;
39 ++result;
40 }
41 return result;
42 }
43
44 /*
45 * Calculates the distance directly using a lookup table. Very fast, esp.
46 * compared to hypot(), but less accurate.
47 *
48 * Produces results exactly as (int) hypot( (double)x, (double)y) up to
49 * hypot(HYPOTMIN,HYPOTMIN), and then loses accuracy in the trailing digits.
50 * With HYPOTMIN = 1000, error is .01% at 200000,200000.
51 *
52 * Bill Dyess
53 */
54
55 #define HYPOTMIN 1000
56 int hypotlookup[] = {
57 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000,
58 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000,
59 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000,
60 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000,
61 1000, 1000, 1000, 1000, 1000, 1001, 1001, 1001, 1001, 1001,
62 1001, 1001, 1001, 1001, 1001, 1001, 1001, 1001, 1001, 1001,
63 1001, 1001, 1001, 1001, 1002, 1002, 1002, 1002, 1002, 1002,
64 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1003, 1003,
65 1003, 1003, 1003, 1003, 1003, 1003, 1003, 1003, 1003, 1003,
66 1004, 1004, 1004, 1004, 1004, 1004, 1004, 1004, 1004, 1004,
67 1004, 1005, 1005, 1005, 1005, 1005, 1005, 1005, 1005, 1005,
68 1006, 1006, 1006, 1006, 1006, 1006, 1006, 1006, 1006, 1007,
69 1007, 1007, 1007, 1007, 1007, 1007, 1007, 1008, 1008, 1008,
70 1008, 1008, 1008, 1008, 1008, 1009, 1009, 1009, 1009, 1009,
71 1009, 1009, 1010, 1010, 1010, 1010, 1010, 1010, 1010, 1011,
72 1011, 1011, 1011, 1011, 1011, 1011, 1012, 1012, 1012, 1012,
73 1012, 1012, 1013, 1013, 1013, 1013, 1013, 1013, 1014, 1014,
74 1014, 1014, 1014, 1014, 1015, 1015, 1015, 1015, 1015, 1015,
75 1016, 1016, 1016, 1016, 1016, 1016, 1017, 1017, 1017, 1017,
76 1017, 1018, 1018, 1018, 1018, 1018, 1019, 1019, 1019, 1019,
77 1019, 1020, 1020, 1020, 1020, 1020, 1020, 1021, 1021, 1021,
78 1021, 1022, 1022, 1022, 1022, 1022, 1023, 1023, 1023, 1023,
79 1023, 1024, 1024, 1024, 1024, 1025, 1025, 1025, 1025, 1025,
80 1026, 1026, 1026, 1026, 1027, 1027, 1027, 1027, 1027, 1028,
81 1028, 1028, 1028, 1029, 1029, 1029, 1029, 1030, 1030, 1030,
82 1030, 1031, 1031, 1031, 1031, 1032, 1032, 1032, 1032, 1032,
83 1033, 1033, 1033, 1034, 1034, 1034, 1034, 1035, 1035, 1035,
84 1035, 1036, 1036, 1036, 1036, 1037, 1037, 1037, 1037, 1038,
85 1038, 1038, 1039, 1039, 1039, 1039, 1040, 1040, 1040, 1040,
86 1041, 1041, 1041, 1042, 1042, 1042, 1042, 1043, 1043, 1043,
87 1044, 1044, 1044, 1044, 1045, 1045, 1045, 1046, 1046, 1046,
88 1046, 1047, 1047, 1047, 1048, 1048, 1048, 1049, 1049, 1049,
89 1049, 1050, 1050, 1050, 1051, 1051, 1051, 1052, 1052, 1052,
90 1053, 1053, 1053, 1053, 1054, 1054, 1054, 1055, 1055, 1055,
91 1056, 1056, 1056, 1057, 1057, 1057, 1058, 1058, 1058, 1059,
92 1059, 1059, 1060, 1060, 1060, 1061, 1061, 1061, 1062, 1062,
93 1062, 1063, 1063, 1063, 1064, 1064, 1064, 1065, 1065, 1065,
94 1066, 1066, 1066, 1067, 1067, 1068, 1068, 1068, 1069, 1069,
95 1069, 1070, 1070, 1070, 1071, 1071, 1071, 1072, 1072, 1072,
96 1073, 1073, 1074, 1074, 1074, 1075, 1075, 1075, 1076, 1076,
97 1077, 1077, 1077, 1078, 1078, 1078, 1079, 1079, 1080, 1080,
98 1080, 1081, 1081, 1081, 1082, 1082, 1083, 1083, 1083, 1084,
99 1084, 1085, 1085, 1085, 1086, 1086, 1086, 1087, 1087, 1088,
100 1088, 1088, 1089, 1089, 1090, 1090, 1090, 1091, 1091, 1092,
101 1092, 1092, 1093, 1093, 1094, 1094, 1094, 1095, 1095, 1096,
102 1096, 1096, 1097, 1097, 1098, 1098, 1099, 1099, 1099, 1100,
103 1100, 1101, 1101, 1101, 1102, 1102, 1103, 1103, 1104, 1104,
104 1104, 1105, 1105, 1106, 1106, 1107, 1107, 1107, 1108, 1108,
105 1109, 1109, 1110, 1110, 1110, 1111, 1111, 1112, 1112, 1113,
106 1113, 1114, 1114, 1114, 1115, 1115, 1116, 1116, 1117, 1117,
107 1118, 1118, 1118, 1119, 1119, 1120, 1120, 1121, 1121, 1122,
108 1122, 1122, 1123, 1123, 1124, 1124, 1125, 1125, 1126, 1126,
109 1127, 1127, 1128, 1128, 1128, 1129, 1129, 1130, 1130, 1131,
110 1131, 1132, 1132, 1133, 1133, 1134, 1134, 1135, 1135, 1136,
111 1136, 1136, 1137, 1137, 1138, 1138, 1139, 1139, 1140, 1140,
112 1141, 1141, 1142, 1142, 1143, 1143, 1144, 1144, 1145, 1145,
113 1146, 1146, 1147, 1147, 1148, 1148, 1149, 1149, 1150, 1150,
114 1151, 1151, 1152, 1152, 1153, 1153, 1154, 1154, 1155, 1155,
115 1156, 1156, 1157, 1157, 1158, 1158, 1159, 1159, 1160, 1160,
116 1161, 1161, 1162, 1162, 1163, 1163, 1164, 1164, 1165, 1165,
117 1166, 1166, 1167, 1167, 1168, 1168, 1169, 1169, 1170, 1170,
118 1171, 1171, 1172, 1172, 1173, 1173, 1174, 1175, 1175, 1176,
119 1176, 1177, 1177, 1178, 1178, 1179, 1179, 1180, 1180, 1181,
120 1181, 1182, 1182, 1183, 1184, 1184, 1185, 1185, 1186, 1186,
121 1187, 1187, 1188, 1188, 1189, 1189, 1190, 1191, 1191, 1192,
122 1192, 1193, 1193, 1194, 1194, 1195, 1195, 1196, 1197, 1197,
123 1198, 1198, 1199, 1199, 1200, 1200, 1201, 1202, 1202, 1203,
124 1203, 1204, 1204, 1205, 1205, 1206, 1207, 1207, 1208, 1208,
125 1209, 1209, 1210, 1210, 1211, 1212, 1212, 1213, 1213, 1214,
126 1214, 1215, 1216, 1216, 1217, 1217, 1218, 1218, 1219, 1220,
127 1220, 1221, 1221, 1222, 1222, 1223, 1224, 1224, 1225, 1225,
128 1226, 1226, 1227, 1228, 1228, 1229, 1229, 1230, 1231, 1231,
129 1232, 1232, 1233, 1233, 1234, 1235, 1235, 1236, 1236, 1237,
130 1238, 1238, 1239, 1239, 1240, 1241, 1241, 1242, 1242, 1243,
131 1244, 1244, 1245, 1245, 1246, 1247, 1247, 1248, 1248, 1249,
132 1250, 1250, 1251, 1251, 1252, 1253, 1253, 1254, 1254, 1255,
133 1256, 1256, 1257, 1257, 1258, 1259, 1259, 1260, 1260, 1261,
134 1262, 1262, 1263, 1263, 1264, 1265, 1265, 1266, 1266, 1267,
135 1268, 1268, 1269, 1270, 1270, 1271, 1271, 1272, 1273, 1273,
136 1274, 1275, 1275, 1276, 1276, 1277, 1278, 1278, 1279, 1280,
137 1280, 1281, 1281, 1282, 1283, 1283, 1284, 1285, 1285, 1286,
138 1286, 1287, 1288, 1288, 1289, 1290, 1290, 1291, 1291, 1292,
139 1293, 1293, 1294, 1295, 1295, 1296, 1297, 1297, 1298, 1298,
140 1299, 1300, 1300, 1301, 1302, 1302, 1303, 1304, 1304, 1305,
141 1305, 1306, 1307, 1307, 1308, 1309, 1309, 1310, 1311, 1311,
142 1312, 1313, 1313, 1314, 1315, 1315, 1316, 1316, 1317, 1318,
143 1318, 1319, 1320, 1320, 1321, 1322, 1322, 1323, 1324, 1324,
144 1325, 1326, 1326, 1327, 1328, 1328, 1329, 1330, 1330, 1331,
145 1332, 1332, 1333, 1334, 1334, 1335, 1336, 1336, 1337, 1338,
146 1338, 1339, 1340, 1340, 1341, 1342, 1342, 1343, 1344, 1344,
147 1345, 1346, 1346, 1347, 1348, 1348, 1349, 1350, 1350, 1351,
148 1352, 1352, 1353, 1354, 1354, 1355, 1356, 1356, 1357, 1358,
149 1358, 1359, 1360, 1360, 1361, 1362, 1362, 1363, 1364, 1364,
150 1365, 1366, 1366, 1367, 1368, 1369, 1369, 1370, 1371, 1371,
151 1372, 1373, 1373, 1374, 1375, 1375, 1376, 1377, 1377, 1378,
152 1379, 1380, 1380, 1381, 1382, 1382, 1383, 1384, 1384, 1385,
153 1386, 1386, 1387, 1388, 1388, 1389, 1390, 1391, 1391, 1392,
154 1393, 1393, 1394, 1395, 1395, 1396, 1397, 1398, 1398, 1399,
155 1400, 1400, 1401, 1402, 1402, 1403, 1404, 1405, 1405, 1406,
156 1407, 1407, 1408, 1409, 1409, 1410, 1411, 1412, 1412, 1413,
157 1414
158 };
159
160 int
161 ihypot(x, y)
162 int x, y;
163 {
164 int max, min;
165
166 x = (x < 0) ? -x : x;
167 y = (y < 0) ? -y : y;
168 if (x > y)
169 {
170 max = x;
171 min = y;
172 }
173 else
174 {
175 max = y;
176 min = x;
177 }
178 if (max == 0)
179 return 0;
180 /* if(max < 32768) return isqrt(max*max+min*min); */
181 return hypotlookup[HYPOTMIN * min / max] * max / HYPOTMIN;
182 }
183
184 #if 0
185 /* code to calculate the lookup table. */
186 #include<math.h>
187
188 int
189 main(int argc, char **argv)
190 {
191 int i, j, max;
192
193 if (argc != 2)
194 {
195 printf("Usage: %s <size of ihypot() lookup table>\n", argv[0]);
196 return 0;
197 }
198 max = atoi(argv[1]);
199 printf("#define HYPOTMIN %d\nint hypotlookup[] = {\n %d", max, max);
200 for (i = 1, j = 1; i <= max; i++, j++)
201 {
202 if (j % 10 == 0)
203 printf(",\n ");
204 else
205 printf(", ");
206 printf("%d", (int) hypot((double) i, (double) max));
207 }
208 printf("\n};\n");
209 return 0;
210 }
211 #endif /* 0 */
212
213 #if 0
214 /* code to test various routines */
215 int
216 main(int argc, char **argv)
217 {
218 if (argc != 3)
219 {
220 printf("Usage: %s <x> <y>\n", argv[0]);
221 return 0;
222 }
223 printf("hypot = %d\n", ihypot(atoi(argv[1]), atoi(argv[2])));
224 return 0;
225 }
226 #endif /* 0 */