src/misc/powers.h

   1 #include <stdint.h>
   2
   3 #define npowers     87
   4 #define steppowers  8
   5 #define firstpower -348 /* 10 ^ -348 */
   6
   7 #define expmax     -32
   8 #define expmin     -60
   9
  10
  11 typedef struct Fp {
  12     uint64_t frac;
  13     int exp;
  14 } Fp;
  15
  16 static Fp powers_ten[] = {
  17     { 18054884314459144840U, -1220 }, { 13451937075301367670U, -1193 },
  18     { 10022474136428063862U, -1166 }, { 14934650266808366570U, -1140 },
  19     { 11127181549972568877U, -1113 }, { 16580792590934885855U, -1087 },
  20     { 12353653155963782858U, -1060 }, { 18408377700990114895U, -1034 },
  21     { 13715310171984221708U, -1007 }, { 10218702384817765436U, -980 },
  22     { 15227053142812498563U, -954 },  { 11345038669416679861U, -927 },
  23     { 16905424996341287883U, -901 },  { 12595523146049147757U, -874 },
  24     { 9384396036005875287U,  -847 },  { 13983839803942852151U, -821 },
  25     { 10418772551374772303U, -794 },  { 15525180923007089351U, -768 },
  26     { 11567161174868858868U, -741 },  { 17236413322193710309U, -715 },
  27     { 12842128665889583758U, -688 },  { 9568131466127621947U,  -661 },
  28     { 14257626930069360058U, -635 },  { 10622759856335341974U, -608 },
  29     { 15829145694278690180U, -582 },  { 11793632577567316726U, -555 },
  30     { 17573882009934360870U, -529 },  { 13093562431584567480U, -502 },
  31     { 9755464219737475723U,  -475 },  { 14536774485912137811U, -449 },
  32     { 10830740992659433045U, -422 },  { 16139061738043178685U, -396 },
  33     { 12024538023802026127U, -369 },  { 17917957937422433684U, -343 },
  34     { 13349918974505688015U, -316 },  { 9946464728195732843U,  -289 },
  35     { 14821387422376473014U, -263 },  { 11042794154864902060U, -236 },
  36     { 16455045573212060422U, -210 },  { 12259964326927110867U, -183 },
  37     { 18268770466636286478U, -157 },  { 13611294676837538539U, -130 },
  38     { 10141204801825835212U, -103 },  { 15111572745182864684U, -77 },
  39     { 11258999068426240000U, -50 },   { 16777216000000000000U, -24 },
  40     { 12500000000000000000U,   3 },   { 9313225746154785156U,   30 },
  41     { 13877787807814456755U,  56 },   { 10339757656912845936U,  83 },
  42     { 15407439555097886824U, 109 },   { 11479437019748901445U, 136 },
  43     { 17105694144590052135U, 162 },   { 12744735289059618216U, 189 },
  44     { 9495567745759798747U,  216 },   { 14149498560666738074U, 242 },
  45     { 10542197943230523224U, 269 },   { 15709099088952724970U, 295 },
  46     { 11704190886730495818U, 322 },   { 17440603504673385349U, 348 },
  47     { 12994262207056124023U, 375 },   { 9681479787123295682U,  402 },
  48     { 14426529090290212157U, 428 },   { 10748601772107342003U, 455 },
  49     { 16016664761464807395U, 481 },   { 11933345169920330789U, 508 },
  50     { 17782069995880619868U, 534 },   { 13248674568444952270U, 561 },
  51     { 9871031767461413346U,  588 },   { 14708983551653345445U, 614 },
  52     { 10959046745042015199U, 641 },   { 16330252207878254650U, 667 },
  53     { 12166986024289022870U, 694 },   { 18130221999122236476U, 720 },
  54     { 13508068024458167312U, 747 },   { 10064294952495520794U, 774 },
  55     { 14996968138956309548U, 800 },   { 11173611982879273257U, 827 },
  56     { 16649979327439178909U, 853 },   { 12405201291620119593U, 880 },
  57     { 9242595204427927429U,  907 },   { 13772540099066387757U, 933 },
  58     { 10261342003245940623U, 960 },   { 15290591125556738113U, 986 },
  59     { 11392378155556871081U, 1013 },  { 16975966327722178521U, 1039 },
  60     { 12648080533535911531U, 1066 }
  61 };
  62
  63 static Fp find_cachedpow10(int exp, int* k)
  64 {
  65     const double one_log_ten = 0.30102999566398114;
  66
  67     int approx = -(exp + npowers) * one_log_ten;
  68     int idx = (approx - firstpower) / steppowers;
  69
  70     while(1) {
  71         int current = exp + powers_ten[idx].exp + 64;
  72
  73         if(current < expmin) {
  74             idx++;
  75             continue;
  76         }
  77
  78         if(current > expmax) {
  79             idx--;
  80             continue;
  81         }
  82
  83         *k = (firstpower + idx * steppowers);
  84
  85         return powers_ten[idx];
  86     }
  87 }