|
4
|
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 */
|
