--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/imath.c	Sat Dec 06 04:37:03 1997 +0000
@@ -0,0 +1,226 @@
+/*--------------------------------------------------------------------------
+NETREK II -- Paradise
+
+Permission to use, copy, modify, and distribute this software and its
+documentation, or any derivative works thereof, for any NON-COMMERCIAL
+purpose and without fee is hereby granted, provided that this copyright
+notice appear in all copies.  No representations are made about the
+suitability of this software for any purpose.  This software is provided
+"as is" without express or implied warranty.
+
+    Xtrek Copyright 1986                            Chris Guthrie
+    Netrek (Xtrek II) Copyright 1989                Kevin P. Smith
+                                                    Scott Silvey
+    Paradise II (Netrek II) Copyright 1993          Larry Denys
+                                                    Kurt Olsen
+                                                    Brandon Gillespie
+--------------------------------------------------------------------------*/
+
+/* collection of integer math routines. [BDyess] */
+
+/*
+ * Based on (n+1)^2 = n^2 + 2n + 1 given that	1^2 = 1, then 2^2 = 1 + (2 +
+ * 1) = 1 + 3 = 4 3^2 = 4 + (4 + 1) = 4 + 5 = 1 + 3 + 5 = 9 4^2 = 9 + (6 + 1)
+ * = 9 + 7 = 1 + 3 + 5 + 7 = 16 ... In other words, a square number can be
+ * express as the sum of the series n^2 = 1 + 3 + ... + (2n-1)
+ * 
+ * Note that NO multiplication or floating point math is needed. [BDyess]
+ */
+int
+isqrt(n)
+  int n;
+{
+  int result = 0, sum = 1, prev = 1;
+
+  while (sum <= n)
+  {
+    prev += 2;
+    sum += prev;
+    ++result;
+  }
+  return result;
+}
+
+/*
+ * Calculates the distance directly using a lookup table. Very fast, esp.
+ * compared to hypot(), but less accurate.
+ * 
+ * Produces results exactly as (int) hypot( (double)x, (double)y) up to
+ * hypot(HYPOTMIN,HYPOTMIN), and then loses accuracy in the trailing digits.
+ * With HYPOTMIN = 1000, error is .01% at 200000,200000.
+ * 
+ * Bill Dyess
+ */
+
+#define HYPOTMIN 1000
+int hypotlookup[] = {
+  1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000,
+  1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000,
+  1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000,
+  1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000,
+  1000, 1000, 1000, 1000, 1000, 1001, 1001, 1001, 1001, 1001,
+  1001, 1001, 1001, 1001, 1001, 1001, 1001, 1001, 1001, 1001,
+  1001, 1001, 1001, 1001, 1002, 1002, 1002, 1002, 1002, 1002,
+  1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1003, 1003,
+  1003, 1003, 1003, 1003, 1003, 1003, 1003, 1003, 1003, 1003,
+  1004, 1004, 1004, 1004, 1004, 1004, 1004, 1004, 1004, 1004,
+  1004, 1005, 1005, 1005, 1005, 1005, 1005, 1005, 1005, 1005,
+  1006, 1006, 1006, 1006, 1006, 1006, 1006, 1006, 1006, 1007,
+  1007, 1007, 1007, 1007, 1007, 1007, 1007, 1008, 1008, 1008,
+  1008, 1008, 1008, 1008, 1008, 1009, 1009, 1009, 1009, 1009,
+  1009, 1009, 1010, 1010, 1010, 1010, 1010, 1010, 1010, 1011,
+  1011, 1011, 1011, 1011, 1011, 1011, 1012, 1012, 1012, 1012,
+  1012, 1012, 1013, 1013, 1013, 1013, 1013, 1013, 1014, 1014,
+  1014, 1014, 1014, 1014, 1015, 1015, 1015, 1015, 1015, 1015,
+  1016, 1016, 1016, 1016, 1016, 1016, 1017, 1017, 1017, 1017,
+  1017, 1018, 1018, 1018, 1018, 1018, 1019, 1019, 1019, 1019,
+  1019, 1020, 1020, 1020, 1020, 1020, 1020, 1021, 1021, 1021,
+  1021, 1022, 1022, 1022, 1022, 1022, 1023, 1023, 1023, 1023,
+  1023, 1024, 1024, 1024, 1024, 1025, 1025, 1025, 1025, 1025,
+  1026, 1026, 1026, 1026, 1027, 1027, 1027, 1027, 1027, 1028,
+  1028, 1028, 1028, 1029, 1029, 1029, 1029, 1030, 1030, 1030,
+  1030, 1031, 1031, 1031, 1031, 1032, 1032, 1032, 1032, 1032,
+  1033, 1033, 1033, 1034, 1034, 1034, 1034, 1035, 1035, 1035,
+  1035, 1036, 1036, 1036, 1036, 1037, 1037, 1037, 1037, 1038,
+  1038, 1038, 1039, 1039, 1039, 1039, 1040, 1040, 1040, 1040,
+  1041, 1041, 1041, 1042, 1042, 1042, 1042, 1043, 1043, 1043,
+  1044, 1044, 1044, 1044, 1045, 1045, 1045, 1046, 1046, 1046,
+  1046, 1047, 1047, 1047, 1048, 1048, 1048, 1049, 1049, 1049,
+  1049, 1050, 1050, 1050, 1051, 1051, 1051, 1052, 1052, 1052,
+  1053, 1053, 1053, 1053, 1054, 1054, 1054, 1055, 1055, 1055,
+  1056, 1056, 1056, 1057, 1057, 1057, 1058, 1058, 1058, 1059,
+  1059, 1059, 1060, 1060, 1060, 1061, 1061, 1061, 1062, 1062,
+  1062, 1063, 1063, 1063, 1064, 1064, 1064, 1065, 1065, 1065,
+  1066, 1066, 1066, 1067, 1067, 1068, 1068, 1068, 1069, 1069,
+  1069, 1070, 1070, 1070, 1071, 1071, 1071, 1072, 1072, 1072,
+  1073, 1073, 1074, 1074, 1074, 1075, 1075, 1075, 1076, 1076,
+  1077, 1077, 1077, 1078, 1078, 1078, 1079, 1079, 1080, 1080,
+  1080, 1081, 1081, 1081, 1082, 1082, 1083, 1083, 1083, 1084,
+  1084, 1085, 1085, 1085, 1086, 1086, 1086, 1087, 1087, 1088,
+  1088, 1088, 1089, 1089, 1090, 1090, 1090, 1091, 1091, 1092,
+  1092, 1092, 1093, 1093, 1094, 1094, 1094, 1095, 1095, 1096,
+  1096, 1096, 1097, 1097, 1098, 1098, 1099, 1099, 1099, 1100,
+  1100, 1101, 1101, 1101, 1102, 1102, 1103, 1103, 1104, 1104,
+  1104, 1105, 1105, 1106, 1106, 1107, 1107, 1107, 1108, 1108,
+  1109, 1109, 1110, 1110, 1110, 1111, 1111, 1112, 1112, 1113,
+  1113, 1114, 1114, 1114, 1115, 1115, 1116, 1116, 1117, 1117,
+  1118, 1118, 1118, 1119, 1119, 1120, 1120, 1121, 1121, 1122,
+  1122, 1122, 1123, 1123, 1124, 1124, 1125, 1125, 1126, 1126,
+  1127, 1127, 1128, 1128, 1128, 1129, 1129, 1130, 1130, 1131,
+  1131, 1132, 1132, 1133, 1133, 1134, 1134, 1135, 1135, 1136,
+  1136, 1136, 1137, 1137, 1138, 1138, 1139, 1139, 1140, 1140,
+  1141, 1141, 1142, 1142, 1143, 1143, 1144, 1144, 1145, 1145,
+  1146, 1146, 1147, 1147, 1148, 1148, 1149, 1149, 1150, 1150,
+  1151, 1151, 1152, 1152, 1153, 1153, 1154, 1154, 1155, 1155,
+  1156, 1156, 1157, 1157, 1158, 1158, 1159, 1159, 1160, 1160,
+  1161, 1161, 1162, 1162, 1163, 1163, 1164, 1164, 1165, 1165,
+  1166, 1166, 1167, 1167, 1168, 1168, 1169, 1169, 1170, 1170,
+  1171, 1171, 1172, 1172, 1173, 1173, 1174, 1175, 1175, 1176,
+  1176, 1177, 1177, 1178, 1178, 1179, 1179, 1180, 1180, 1181,
+  1181, 1182, 1182, 1183, 1184, 1184, 1185, 1185, 1186, 1186,
+  1187, 1187, 1188, 1188, 1189, 1189, 1190, 1191, 1191, 1192,
+  1192, 1193, 1193, 1194, 1194, 1195, 1195, 1196, 1197, 1197,
+  1198, 1198, 1199, 1199, 1200, 1200, 1201, 1202, 1202, 1203,
+  1203, 1204, 1204, 1205, 1205, 1206, 1207, 1207, 1208, 1208,
+  1209, 1209, 1210, 1210, 1211, 1212, 1212, 1213, 1213, 1214,
+  1214, 1215, 1216, 1216, 1217, 1217, 1218, 1218, 1219, 1220,
+  1220, 1221, 1221, 1222, 1222, 1223, 1224, 1224, 1225, 1225,
+  1226, 1226, 1227, 1228, 1228, 1229, 1229, 1230, 1231, 1231,
+  1232, 1232, 1233, 1233, 1234, 1235, 1235, 1236, 1236, 1237,
+  1238, 1238, 1239, 1239, 1240, 1241, 1241, 1242, 1242, 1243,
+  1244, 1244, 1245, 1245, 1246, 1247, 1247, 1248, 1248, 1249,
+  1250, 1250, 1251, 1251, 1252, 1253, 1253, 1254, 1254, 1255,
+  1256, 1256, 1257, 1257, 1258, 1259, 1259, 1260, 1260, 1261,
+  1262, 1262, 1263, 1263, 1264, 1265, 1265, 1266, 1266, 1267,
+  1268, 1268, 1269, 1270, 1270, 1271, 1271, 1272, 1273, 1273,
+  1274, 1275, 1275, 1276, 1276, 1277, 1278, 1278, 1279, 1280,
+  1280, 1281, 1281, 1282, 1283, 1283, 1284, 1285, 1285, 1286,
+  1286, 1287, 1288, 1288, 1289, 1290, 1290, 1291, 1291, 1292,
+  1293, 1293, 1294, 1295, 1295, 1296, 1297, 1297, 1298, 1298,
+  1299, 1300, 1300, 1301, 1302, 1302, 1303, 1304, 1304, 1305,
+  1305, 1306, 1307, 1307, 1308, 1309, 1309, 1310, 1311, 1311,
+  1312, 1313, 1313, 1314, 1315, 1315, 1316, 1316, 1317, 1318,
+  1318, 1319, 1320, 1320, 1321, 1322, 1322, 1323, 1324, 1324,
+  1325, 1326, 1326, 1327, 1328, 1328, 1329, 1330, 1330, 1331,
+  1332, 1332, 1333, 1334, 1334, 1335, 1336, 1336, 1337, 1338,
+  1338, 1339, 1340, 1340, 1341, 1342, 1342, 1343, 1344, 1344,
+  1345, 1346, 1346, 1347, 1348, 1348, 1349, 1350, 1350, 1351,
+  1352, 1352, 1353, 1354, 1354, 1355, 1356, 1356, 1357, 1358,
+  1358, 1359, 1360, 1360, 1361, 1362, 1362, 1363, 1364, 1364,
+  1365, 1366, 1366, 1367, 1368, 1369, 1369, 1370, 1371, 1371,
+  1372, 1373, 1373, 1374, 1375, 1375, 1376, 1377, 1377, 1378,
+  1379, 1380, 1380, 1381, 1382, 1382, 1383, 1384, 1384, 1385,
+  1386, 1386, 1387, 1388, 1388, 1389, 1390, 1391, 1391, 1392,
+  1393, 1393, 1394, 1395, 1395, 1396, 1397, 1398, 1398, 1399,
+  1400, 1400, 1401, 1402, 1402, 1403, 1404, 1405, 1405, 1406,
+  1407, 1407, 1408, 1409, 1409, 1410, 1411, 1412, 1412, 1413,
+  1414
+};
+
+int 
+ihypot(x, y)
+  int x, y;
+{
+  int max, min;
+
+  x = (x < 0) ? -x : x;
+  y = (y < 0) ? -y : y;
+  if (x > y)
+  {
+    max = x;
+    min = y;
+  }
+  else
+  {
+    max = y;
+    min = x;
+  }
+  if (max == 0)
+    return 0;
+  /* if(max < 32768) return isqrt(max*max+min*min); */
+  return hypotlookup[HYPOTMIN * min / max] * max / HYPOTMIN;
+}
+
+#if 0
+/* code to calculate the lookup table. */
+#include<math.h>
+
+int 
+main(int argc, char **argv)
+{
+  int i, j, max;
+
+  if (argc != 2)
+  {
+    printf("Usage: %s <size of ihypot() lookup table>\n", argv[0]);
+    return 0;
+  }
+  max = atoi(argv[1]);
+  printf("#define HYPOTMIN %d\nint hypotlookup[] = {\n  %d", max, max);
+  for (i = 1, j = 1; i <= max; i++, j++)
+  {
+    if (j % 10 == 0)
+      printf(",\n  ");
+    else
+      printf(", ");
+    printf("%d", (int) hypot((double) i, (double) max));
+  }
+  printf("\n};\n");
+  return 0;
+}
+#endif				/* 0 */
+
+#if 0
+/* code to test various routines */
+int 
+main(int argc, char **argv)
+{
+  if (argc != 3)
+  {
+    printf("Usage: %s <x> <y>\n", argv[0]);
+    return 0;
+  }
+  printf("hypot = %d\n", ihypot(atoi(argv[1]), atoi(argv[2])));
+  return 0;
+}
+#endif				/* 0 */