maths/tables.c

   1 /*
   2 THE COMPUTER CODE CONTAINED HEREIN IS THE SOLE PROPERTY OF PARALLAX
   3 SOFTWARE CORPORATION ("PARALLAX").  PARALLAX, IN DISTRIBUTING THE CODE TO
   4 END-USERS, AND SUBJECT TO ALL OF THE TERMS AND CONDITIONS HEREIN, GRANTS A
   5 ROYALTY-FREE, PERPETUAL LICENSE TO SUCH END-USERS FOR USE BY SUCH END-USERS
   6 IN USING, DISPLAYING,  AND CREATING DERIVATIVE WORKS THEREOF, SO LONG AS
   7 SUCH USE, DISPLAY OR CREATION IS FOR NON-COMMERCIAL, ROYALTY OR REVENUE
   8 FREE PURPOSES.  IN NO EVENT SHALL THE END-USER USE THE COMPUTER CODE
   9 CONTAINED HEREIN FOR REVENUE-BEARING PURPOSES.  THE END-USER UNDERSTANDS
  10 AND AGREES TO THE TERMS HEREIN AND ACCEPTS THE SAME BY USE OF THIS FILE.
  11 COPYRIGHT 1993-1998 PARALLAX SOFTWARE CORPORATION.  ALL RIGHTS RESERVED.
  12 */
  13 /*
  14  * $Source: /cvs/cvsroot/d2x/maths/tables.c,v $
  15  * $Revision: 1.2 $
  16  * $Author: bradleyb $
  17  * $Date: 2001-01-31 15:18:04 $
  18  *
  19  * C version of fixed point library
  20  *
  21  * $Log: not supported by cvs2svn $
  22  * Revision 1.1.1.1  2001/01/19 03:29:58  bradleyb
  23  * Import of d2x-0.0.8
  24  *
  25  * Revision 1.1.1.1  1999/06/14 22:13:38  donut
  26  * Import of d1x 1.37 source.
  27  *
  28  * Revision 1.2  1995/08/31  15:44:36  allender
  29  * ..
  30  *
  31  * Revision 1.1  1995/04/17  11:38:04  allender
  32  * Initial revision
  33  *
  34 */
  35
  36 #ifdef HAVE_CONFIG_H
  37 #include <conf.h>
  38 #endif
  39
  40 #include "maths.h"
  41
  42 ubyte guess_table[] = {
  43         1,
  44         1,1,1,
  45         2,2,2,2,2,
  46         3,3,3,3,3,3,3,
  47         4,4,4,4,4,4,4,4,4,
  48         5,5,5,5,5,5,5,5,5,5,5,
  49         6,6,6,6,6,6,6,6,6,6,6,6,6,
  50         7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  51         8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
  52         9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,
  53         10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,
  54         11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,
  55         12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,
  56         13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,
  57         14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,
  58         15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15
  59 };
  60
  61 short sincos_table[] = {
  62         0,
  63         402,
  64         804,
  65         1205,
  66         1606,
  67         2006,
  68         2404,
  69         2801,
  70         3196,
  71         3590,
  72         3981,
  73         4370,
  74         4756,
  75         5139,
  76         5520,
  77         5897,
  78         6270,
  79         6639,
  80         7005,
  81         7366,
  82         7723,
  83         8076,
  84         8423,
  85         8765,
  86         9102,
  87         9434,
  88         9760,
  89         10080,
  90         10394,
  91         10702,
  92         11003,
  93         11297,
  94         11585,
  95         11866,
  96         12140,
  97         12406,
  98         12665,
  99         12916,
 100         13160,
 101         13395,
 102         13623,
 103         13842,
 104         14053,
 105         14256,
 106         14449,
 107         14635,
 108         14811,
 109         14978,
 110         15137,
 111         15286,
 112         15426,
 113         15557,
 114         15679,
 115         15791,
 116         15893,
 117         15986,
 118         16069,
 119         16143,
 120         16207,
 121         16261,
 122         16305,
 123         16340,
 124         16364,
 125         16379,
 126 //cos_table
 127         16384,
 128         16379,
 129         16364,
 130         16340,
 131         16305,
 132         16261,
 133         16207,
 134         16143,
 135         16069,
 136         15986,
 137         15893,
 138         15791,
 139         15679,
 140         15557,
 141         15426,
 142         15286,
 143         15137,
 144         14978,
 145         14811,
 146         14635,
 147         14449,
 148         14256,
 149         14053,
 150         13842,
 151         13623,
 152         13395,
 153         13160,
 154         12916,
 155         12665,
 156         12406,
 157         12140,
 158         11866,
 159         11585,
 160         11297,
 161         11003,
 162         10702,
 163         10394,
 164         10080,
 165         9760,
 166         9434,
 167         9102,
 168         8765,
 169         8423,
 170         8076,
 171         7723,
 172         7366,
 173         7005,
 174         6639,
 175         6270,
 176         5897,
 177         5520,
 178         5139,
 179         4756,
 180         4370,
 181         3981,
 182         3590,
 183         3196,
 184         2801,
 185         2404,
 186         2006,
 187         1606,
 188         1205,
 189         804,
 190         402,
 191         0,
 192         -402,
 193         -804,
 194         -1205,
 195         -1606,
 196         -2006,
 197         -2404,
 198         -2801,
 199         -3196,
 200         -3590,
 201         -3981,
 202         -4370,
 203         -4756,
 204         -5139,
 205         -5520,
 206         -5897,
 207         -6270,
 208         -6639,
 209         -7005,
 210         -7366,
 211         -7723,
 212         -8076,
 213         -8423,
 214         -8765,
 215         -9102,
 216         -9434,
 217         -9760,
 218         -10080,
 219         -10394,
 220         -10702,
 221         -11003,
 222         -11297,
 223         -11585,
 224         -11866,
 225         -12140,
 226         -12406,
 227         -12665,
 228         -12916,
 229         -13160,
 230         -13395,
 231         -13623,
 232         -13842,
 233         -14053,
 234         -14256,
 235         -14449,
 236         -14635,
 237         -14811,
 238         -14978,
 239         -15137,
 240         -15286,
 241         -15426,
 242         -15557,
 243         -15679,
 244         -15791,
 245         -15893,
 246         -15986,
 247         -16069,
 248         -16143,
 249         -16207,
 250         -16261,
 251         -16305,
 252         -16340,
 253         -16364,
 254         -16379,
 255         -16384,
 256         -16379,
 257         -16364,
 258         -16340,
 259         -16305,
 260         -16261,
 261         -16207,
 262         -16143,
 263         -16069,
 264         -15986,
 265         -15893,
 266         -15791,
 267         -15679,
 268         -15557,
 269         -15426,
 270         -15286,
 271         -15137,
 272         -14978,
 273         -14811,
 274         -14635,
 275         -14449,
 276         -14256,
 277         -14053,
 278         -13842,
 279         -13623,
 280         -13395,
 281         -13160,
 282         -12916,
 283         -12665,
 284         -12406,
 285         -12140,
 286         -11866,
 287         -11585,
 288         -11297,
 289         -11003,
 290         -10702,
 291         -10394,
 292         -10080,
 293         -9760,
 294         -9434,
 295         -9102,
 296         -8765,
 297         -8423,
 298         -8076,
 299         -7723,
 300         -7366,
 301         -7005,
 302         -6639,
 303         -6270,
 304         -5897,
 305         -5520,
 306         -5139,
 307         -4756,
 308         -4370,
 309         -3981,
 310         -3590,
 311         -3196,
 312         -2801,
 313         -2404,
 314         -2006,
 315         -1606,
 316         -1205,
 317         -804,
 318         -402,
 319         0,
 320         402,
 321         804,
 322         1205,
 323         1606,
 324         2006,
 325         2404,
 326         2801,
 327         3196,
 328         3590,
 329         3981,
 330         4370,
 331         4756,
 332         5139,
 333         5520,
 334         5897,
 335         6270,
 336         6639,
 337         7005,
 338         7366,
 339         7723,
 340         8076,
 341         8423,
 342         8765,
 343         9102,
 344         9434,
 345         9760,
 346         10080,
 347         10394,
 348         10702,
 349         11003,
 350         11297,
 351         11585,
 352         11866,
 353         12140,
 354         12406,
 355         12665,
 356         12916,
 357         13160,
 358         13395,
 359         13623,
 360         13842,
 361         14053,
 362         14256,
 363         14449,
 364         14635,
 365         14811,
 366         14978,
 367         15137,
 368         15286,
 369         15426,
 370         15557,
 371         15679,
 372         15791,
 373         15893,
 374         15986,
 375         16069,
 376         16143,
 377         16207,
 378         16261,
 379         16305,
 380         16340,
 381         16364,
 382         16379,
 383         16384
 384 };
 385
 386 ushort asin_table[] = {
 387         0,
 388         41,
 389         81,
 390         122,
 391         163,
 392         204,
 393         244,
 394         285,
 395         326,
 396         367,
 397         408,
 398         448,
 399         489,
 400         530,
 401         571,
 402         612,
 403         652,
 404         693,
 405         734,
 406         775,
 407         816,
 408         857,
 409         897,
 410         938,
 411         979,
 412         1020,
 413         1061,
 414         1102,
 415         1143,
 416         1184,
 417         1225,
 418         1266,
 419         1307,
 420         1348,
 421         1389,
 422         1431,
 423         1472,
 424         1513,
 425         1554,
 426         1595,
 427         1636,
 428         1678,
 429         1719,
 430         1760,
 431         1802,
 432         1843,
 433         1884,
 434         1926,
 435         1967,
 436         2009,
 437         2050,
 438         2092,
 439         2134,
 440         2175,
 441         2217,
 442         2259,
 443         2300,
 444         2342,
 445         2384,
 446         2426,
 447         2468,
 448         2510,
 449         2551,
 450         2593,
 451         2636,
 452         2678,
 453         2720,
 454         2762,
 455         2804,
 456         2847,
 457         2889,
 458         2931,
 459         2974,
 460         3016,
 461         3059,
 462         3101,
 463         3144,
 464         3187,
 465         3229,
 466         3272,
 467         3315,
 468         3358,
 469         3401,
 470         3444,
 471         3487,
 472         3530,
 473         3573,
 474         3617,
 475         3660,
 476         3704,
 477         3747,
 478         3791,
 479         3834,
 480         3878,
 481         3922,
 482         3965,
 483         4009,
 484         4053,
 485         4097,
 486         4142,
 487         4186,
 488         4230,
 489         4275,
 490         4319,
 491         4364,
 492         4408,
 493         4453,
 494         4498,
 495         4543,
 496         4588,
 497         4633,
 498         4678,
 499         4723,
 500         4768,
 501         4814,
 502         4859,
 503         4905,
 504         4951,
 505         4997,
 506         5043,
 507         5089,
 508         5135,
 509         5181,
 510         5228,
 511         5274,
 512         5321,
 513         5367,
 514         5414,
 515         5461,
 516         5508,
 517         5556,
 518         5603,
 519         5651,
 520         5698,
 521         5746,
 522         5794,
 523         5842,
 524         5890,
 525         5938,
 526         5987,
 527         6035,
 528         6084,
 529         6133,
 530         6182,
 531         6231,
 532         6281,
 533         6330,
 534         6380,
 535         6430,
 536         6480,
 537         6530,
 538         6580,
 539         6631,
 540         6681,
 541         6732,
 542         6783,
 543         6835,
 544         6886,
 545         6938,
 546         6990,
 547         7042,
 548         7094,
 549         7147,
 550         7199,
 551         7252,
 552         7306,
 553         7359,
 554         7413,
 555         7466,
 556         7521,
 557         7575,
 558         7630,
 559         7684,
 560         7740,
 561         7795,
 562         7851,
 563         7907,
 564         7963,
 565         8019,
 566         8076,
 567         8133,
 568         8191,
 569         8249,
 570         8307,
 571         8365,
 572         8424,
 573         8483,
 574         8543,
 575         8602,
 576         8663,
 577         8723,
 578         8784,
 579         8846,
 580         8907,
 581         8970,
 582         9032,
 583         9095,
 584         9159,
 585         9223,
 586         9288,
 587         9353,
 588         9418,
 589         9484,
 590         9551,
 591         9618,
 592         9686,
 593         9754,
 594         9823,
 595         9892,
 596         9963,
 597         10034,
 598         10105,
 599         10177,
 600         10251,
 601         10324,
 602         10399,
 603         10475,
 604         10551,
 605         10628,
 606         10706,
 607         10785,
 608         10866,
 609         10947,
 610         11029,
 611         11113,
 612         11198,
 613         11284,
 614         11371,
 615         11460,
 616         11550,
 617         11642,
 618         11736,
 619         11831,
 620         11929,
 621         12028,
 622         12130,
 623         12234,
 624         12340,
 625         12449,
 626         12561,
 627         12677,
 628         12796,
 629         12919,
 630         13046,
 631         13178,
 632         13315,
 633         13459,
 634         13610,
 635         13770,
 636         13939,
 637         14121,
 638         14319,
 639         14538,
 640         14786,
 641         15079,
 642         15462,
 643         16384,
 644         16384                   //extra for when exacty 1
 645 };
 646
 647 ushort acos_table[] = {
 648         16384,
 649         16343,
 650         16303,
 651         16262,
 652         16221,
 653         16180,
 654         16140,
 655         16099,
 656         16058,
 657         16017,
 658         15976,
 659         15936,
 660         15895,
 661         15854,
 662         15813,
 663         15772,
 664         15732,
 665         15691,
 666         15650,
 667         15609,
 668         15568,
 669         15527,
 670         15487,
 671         15446,
 672         15405,
 673         15364,
 674         15323,
 675         15282,
 676         15241,
 677         15200,
 678         15159,
 679         15118,
 680         15077,
 681         15036,
 682         14995,
 683         14953,
 684         14912,
 685         14871,
 686         14830,
 687         14789,
 688         14748,
 689         14706,
 690         14665,
 691         14624,
 692         14582,
 693         14541,
 694         14500,
 695         14458,
 696         14417,
 697         14375,
 698         14334,
 699         14292,
 700         14250,
 701         14209,
 702         14167,
 703         14125,
 704         14084,
 705         14042,
 706         14000,
 707         13958,
 708         13916,
 709         13874,
 710         13833,
 711         13791,
 712         13748,
 713         13706,
 714         13664,
 715         13622,
 716         13580,
 717         13537,
 718         13495,
 719         13453,
 720         13410,
 721         13368,
 722         13325,
 723         13283,
 724         13240,
 725         13197,
 726         13155,
 727         13112,
 728         13069,
 729         13026,
 730         12983,
 731         12940,
 732         12897,
 733         12854,
 734         12811,
 735         12767,
 736         12724,
 737         12680,
 738         12637,
 739         12593,
 740         12550,
 741         12506,
 742         12462,
 743         12419,
 744         12375,
 745         12331,
 746         12287,
 747         12242,
 748         12198,
 749         12154,
 750         12109,
 751         12065,
 752         12020,
 753         11976,
 754         11931,
 755         11886,
 756         11841,
 757         11796,
 758         11751,
 759         11706,
 760         11661,
 761         11616,
 762         11570,
 763         11525,
 764         11479,
 765         11433,
 766         11387,
 767         11341,
 768         11295,
 769         11249,
 770         11203,
 771         11156,
 772         11110,
 773         11063,
 774         11017,
 775         10970,
 776         10923,
 777         10876,
 778         10828,
 779         10781,
 780         10733,
 781         10686,
 782         10638,
 783         10590,
 784         10542,
 785         10494,
 786         10446,
 787         10397,
 788         10349,
 789         10300,
 790         10251,
 791         10202,
 792         10153,
 793         10103,
 794         10054,
 795         10004,
 796         9954,
 797         9904,
 798         9854,
 799         9804,
 800         9753,
 801         9703,
 802         9652,
 803         9601,
 804         9549,
 805         9498,
 806         9446,
 807         9394,
 808         9342,
 809         9290,
 810         9237,
 811         9185,
 812         9132,
 813         9078,
 814         9025,
 815         8971,
 816         8918,
 817         8863,
 818         8809,
 819         8754,
 820         8700,
 821         8644,
 822         8589,
 823         8533,
 824         8477,
 825         8421,
 826         8365,
 827         8308,
 828         8251,
 829         8193,
 830         8135,
 831         8077,
 832         8019,
 833         7960,
 834         7901,
 835         7841,
 836         7782,
 837         7721,
 838         7661,
 839         7600,
 840         7538,
 841         7477,
 842         7414,
 843         7352,
 844         7289,
 845         7225,
 846         7161,
 847         7096,
 848         7031,
 849         6966,
 850         6900,
 851         6833,
 852         6766,
 853         6698,
 854         6630,
 855         6561,
 856         6492,
 857         6421,
 858         6350,
 859         6279,
 860         6207,
 861         6133,
 862         6060,
 863         5985,
 864         5909,
 865         5833,
 866         5756,
 867         5678,
 868         5599,
 869         5518,
 870         5437,
 871         5355,
 872         5271,
 873         5186,
 874         5100,
 875         5013,
 876         4924,
 877         4834,
 878         4742,
 879         4648,
 880         4553,
 881         4455,
 882         4356,
 883         4254,
 884         4150,
 885         4044,
 886         3935,
 887         3823,
 888         3707,
 889         3588,
 890         3465,
 891         3338,
 892         3206,
 893         3069,
 894         2925,
 895         2774,
 896         2614,
 897         2445,
 898         2263,
 899         2065,
 900         1846,
 901         1598,
 902         1305,
 903         922,
 904         0,
 905         0       //extra for when exacty 1
 906 };
 907
 908 fix isqrt_guess_table[] = {
 909 //      0,
 910         0x80000000,
 911         16777216,11863283,9686330,8388608,7502999,6849269,6341191,
 912         5931641,5592405,5305421,5058520,4843165,4653162,4483899,4331858,
 913         4194304,4069072,3954427,3848957,3751499,3661088,3576914,3498291,
 914         3424634,3355443,3290282,3228776,3170595,3115450,3063086,3013276,
 915         2965820,2920538,2877268,2835867,2796202,2758157,2721623,2686504,
 916         2652710,2620160,2588780,2558501,2529260,2500999,2473665,2447208,
 917         2421582,2396745,2372656,2349280,2326581,2304527,2283089,2262239,
 918         2241949,2222196,2202956,2184207,2165929,2148102,2130708,2113730,
 919         2097152,2080957,2065132,2049663,2034536,2019739,2005260,1991089,
 920         1977213,1963624,1950311,1937266,1924478,1911941,1899645,1887584,
 921         1875749,1864135,1852733,1841538,1830544,1819744,1809133,1798706,
 922         1788457,1778381,1768473,1758730,1749145,1739716,1730437,1721306,
 923         1712317,1703468,1694754,1686173,1677721,1669395,1661191,1653108,
 924         1645141,1637288,1629547,1621914,1614388,1606965,1599644,1592422,
 925         1585297,1578267,1571330,1564483,1557725,1551054,1544467,1537964,
 926         1531543,1525201,1518937,1512750,1506638,1500599,1494633,1488737,
 927         1482910,1477151,1471459,1465832,1460269,1454769,1449330,1443952,
 928         1438634,1433374,1428171,1423024,1417933,1412896,1407912,1402981,
 929         1398101,1393271,1388492,1383761,1379078,1374443,1369853,1365310,
 930         1360811,1356357,1351946,1347578,1343252,1338967,1334723,1330519,
 931         1326355,1322229,1318142,1314092,1310080,1306104,1302164,1298259,
 932         1294390,1290555,1286753,1282985,1279250,1275548,1271877,1268238,
 933         1264630,1261052,1257505,1253987,1250499,1247040,1243609,1240207,
 934         1236832,1233485,1230165,1226871,1223604,1220362,1217147,1213956,
 935         1210791,1207650,1204533,1201441,1198372,1195327,1192304,1189305,
 936         1186328,1183373,1180440,1177529,1174640,1171771,1168924,1166097,
 937         1163290,1160504,1157737,1154991,1152263,1149555,1146866,1144196,
 938         1141544,1138911,1136296,1133699,1131119,1128557,1126013,1123485,
 939         1120974,1118481,1116003,1113542,1111098,1108669,1106256,1103859,
 940         1101478,1099111,1096760,1094424,1092103,1089797,1087505,1085227,
 941         1082964,1080715,1078480,1076258,1074051,1071857,1069676,1067508,
 942         1065354,1063212,1061084,1058968,1056865,1054774,1052696,1050630,
 943         1048576,1046533,1044503,1042485,1040478,1038483,1036499,1034527,
 944         1032566,1030616,1028677,1026748,1024831,1022924,1021028,1019143,
 945         1017268,1015403,1013548,1011704,1009869,1008045,1006230,1004425,
 946         1002630,1000844,999068,997301,995544,993796,992057,990327,
 947         988606,986895,985192,983497,981812,980135,978467,976807,
 948         975155,973512,971878,970251,968633,967022,965420,963825,
 949         962239,960660,959089,957526,955970,954422,952881,951348,
 950         949822,948304,946793,945289,943792,942302,940819,939343,
 951         937874,936412,934957,933509,932067,930632,929204,927782,
 952         926366,924957,923555,922159,920769,919385,918008,916637,
 953         915272,913913,912560,911213,909872,908537,907207,905884,
 954         904566,903254,901948,900648,899353,898063,896779,895501,
 955         894228,892961,891698,890442,889190,887944,886703,885467,
 956         884236,883011,881790,880575,879365,878159,876959,875763,
 957         874572,873386,872205,871029,869858,868691,867529,866371,
 958         865218,864070,862926,861787,860653,859522,858397,857275,
 959         856158,855046,853937,852833,851734,850638,849547,848460,
 960         847377,846298,845223,844153,843086,842024,840965,839911,
 961         838860,837814,836771,835732,834697,833666,832639,831615,
 962         830595,829579,828567,827559,826554,825552,824555,823561,
 963         822570,821583,820600,819620,818644,817671,816702,815736,
 964         814773,813814,812858,811906,810957,810011,809069,808130,
 965         807194,806261,805332,804405,803482,802563,801646,800732,
 966         799822,798915,798010,797109,796211,795316,794424,793535,
 967         792648,791765,790885,790008,789133,788262,787393,786528,
 968         785665,784805,783947,783093,782241,781392,780546,779703,
 969         778862,778024,777189,776356,775527,774699,773875,773053,
 970         772233,771417,770603,769791,768982,768175,767371,766570,
 971         765771,764975,764181,763389,762600,761814,761029,760248,
 972         759468,758691,757917,757145,756375,755607,754842,754079,
 973         753319,752560,751805,751051,750299,749550,748803,748059,
 974         747316,746576,745838,745102,744368,743637,742907,742180,
 975         741455,740732,740011,739292,738575,737861,737148,736438,
 976         735729,735023,734318,733616,732916,732217,731521,730827,
 977         730134,729444,728755,728069,727384,726701,726021,725342,
 978         724665,723990,723317,722645,721976,721308,720643,719979,
 979         719317,718656,717998,717341,716687,716034,715382,714733,
 980         714085,713439,712795,712153,711512,710873,710236,709600,
 981         708966,708334,707704,707075,706448,705822,705198,704576,
 982         703956,703337,702720,702104,701490,700878,700267,699658,
 983         699050,698444,697840,697237,696635,696036,695437,694841,
 984         694246,693652,693060,692469,691880,691293,690707,690122,
 985         689539,688957,688377,687798,687221,686645,686071,685498,
 986         684926,684356,683788,683221,682655,682090,681527,680966,
 987         680405,679847,679289,678733,678178,677625,677073,676522,
 988         675973,675425,674878,674333,673789,673246,672705,672164,
 989         671626,671088,670552,670017,669483,668951,668420,667890,
 990         667361,666834,666308,665783,665259,664737,664216,663696,
 991         663177,662660,662143,661628,661114,660602,660090,659580,
 992         659071,658563,658056,657550,657046,656543,656041,655540,
 993         655040,654541,654043,653547,653052,652558,652065,651573,
 994         651082,650592,650103,649616,649129,648644,648160,647677,
 995         647195,646714,646234,645755,645277,644800,644325,643850,
 996         643376,642904,642432,641962,641492,641024,640557,640090,
 997         639625,639161,638697,638235,637774,637313,636854,636396,
 998         635938,635482,635026,634572,634119,633666,633215,632764,
 999         632315,631866,631418,630972,630526,630081,629637,629194,
1000         628752,628311,627871,627432,626993,626556,626120,625684,
1001         625249,624816,624383,623951,623520,623090,622660,622232,
1002         621804,621378,620952,620527,620103,619680,619258,618836,
1003         618416,617996,617577,617159,616742,616326,615910,615496,
1004         615082,614669,614257,613846,613435,613026,612617,612209,
1005         611802,611395,610990,610585,610181,609778,609375,608974,
1006         608573,608173,607774,607375,606978,606581,606185,605790,
1007         605395,605001,604608,604216,603825,603434,603044,602655,
1008         602266,601879,601492,601106,600720,600335,599952,599568,
1009         599186,598804,598423,598043,597663,597284,596906,596529,
1010         596152,595776,595401,595026,594652,594279,593907,593535,
1011         593164,592793,592424,592055,591686,591319,590952,590585,
1012         590220,589855,589491,589127,588764,588402,588041,587680,
1013         587320,586960,586601,586243,585885,585528,585172,584816,
1014         584462,584107,583754,583400,583048,582696,582345,581995,
1015         581645,581296,580947,580599,580252,579905,579559,579213,
1016         578868,578524,578181,577838,577495,577153,576812,576471,
1017         576131,575792,575453,575115,574777,574440,574104,573768,
1018         573433,573098,572764,572431,572098,571765,571434,571103,
1019         570772,570442,570113,569784,569455,569128,568800,568474,
1020         568148,567822,567497,567173,566849,566526,566203,565881,
1021         565559,565238,564918,564598,564278,563959,563641,563323,
1022         563006,562689,562373,562057,561742,561428,561114,560800,
1023         560487,560174,559862,559551,559240,558930,558620,558310,
1024         558001,557693,557385,557078,556771,556465,556159,555853,
1025         555549,555244,554940,554637,554334,554032,553730,553429,
1026         553128,552828,552528,552228,551929,551631,551333,551036,
1027         550739,550442,550146,549851,549555,549261,548967,548673,
1028         548380,548087,547795,547503,547212,546921,546631,546341,
1029         546051,545762,545474,545186,544898,544611,544324,544038,
1030         543752,543467,543182,542897,542613,542330,542047,541764,
1031         541482,541200,540919,540638,540357,540077,539798,539518,
1032         539240,538961,538683,538406,538129,537852,537576,537300,
1033         537025,536750,536476,536202,535928,535655,535382,535110,
1034         534838,534566,534295,534024,533754,533484,533214,532945,
1035         532677,532408,532140,531873,531606,531339,531073,530807,
1036         530542,530277,530012,529748,529484,529220,528957,528694,
1037         528432,528170,527909,527648,527387,527126,526866,526607,
1038         526348,526089,525830,525572,525315,525057,524800,524544
1039 };
1040