DIV by MUL (last update: 2012-09-21, created: 2012-09-21) back to the list ↑ In 32- and 64-bit signed integers it's possible to divide a number by multiplying it - a trick used by compilers sometime. A good article on this: Optimising pointer subtraction with 2-adic integers. Some code snippet I've created while playing with the above: ```#include  #include  int64_t find_1_div2(int64_t k) {   // a/b = c   // a - const = 1   // c - const   // b - x   // f(x) = 1/x - C   // f'(x) = -1 / x^2   //   // x[n+1] = x[n] - f(x[n]) / f'(x[n])   // x[n+1] = x[n] - (1/x[n] - C) / (-1 / x[n]^2)   // x[n+1] = x[n] + (1/x[n] - C)*(x[n]^2)   // x[n+1] = 2*x[n] - C*x[n]^2   // x[n+1] = x[n] * (2 - C*x[n])   //   // C is my k   int64_t xn = 1;   xn = xn * (2 - k * xn); printf("k=%lli -> x: %lli (test: %lli =?= 1)\n", k, xn, xn*k);   xn = xn * (2 - k * xn); printf("k=%lli -> x: %lli (test: %lli =?= 1)\n", k, xn, xn*k);   xn = xn * (2 - k * xn); printf("k=%lli -> x: %lli (test: %lli =?= 1)\n", k, xn, xn*k);   xn = xn * (2 - k * xn); printf("k=%lli -> x: %lli (test: %lli =?= 1)\n", k, xn, xn*k);   xn = xn * (2 - k * xn); printf("k=%lli -> x: %lli (test: %lli =?= 1)\n", k, xn, xn*k);   xn = xn * (2 - k * xn); printf("k=%lli -> x: %lli (test: %lli =?= 1)\n", k, xn, xn*k);   xn = xn * (2 - k * xn); printf("k=%lli -> x: %lli (test: %lli =?= 1)\n", k, xn, xn*k);   return xn; } int find_1_div(int k) {   int t1 = k;   int t2 = k * 2;   int t3 = k * 3;   int i = INT32_MIN;   for(; i < 0; i++)   {     if(i * t1 == 1 &&        i * t2 == 2 &&        i * t3 == 3)       return i;   }   return 0; } int main(void) {   // 1/7  -> -1227133513   // 1/11 -> -1171354717   find_1_div2(12345);   printf("1/7 -> %i\n", 7, find_1_div2(7));   /*int j;   for(j = 3; j < 1000; j += 2)   {     int div = find_1_div(j);     if(div)       printf("1/%i -> %i\n", j, div);     else       printf("1/%i -> none\n", j);   }*/   return 0; } ``` Results for the first 100 odd numbers in 32-bit ring: ```1/3 -> -1431655765 1/5 -> -858993459 1/7 -> -1227133513 1/9 -> none 1/11 -> -1171354717 1/13 -> -991146299 1/15 -> -286331153 1/17 -> -252645135 1/19 -> none 1/21 -> none 1/23 -> -373475417 1/25 -> -1030792151 1/27 -> none 1/29 -> none 1/31 -> -1108378657 1/33 -> none 1/35 -> -1963413621 1/37 -> -1857283155 1/39 -> -1762037865 1/41 -> -1047552999 1/43 -> none 1/45 -> -1527099483 1/47 -> none 1/49 -> none 1/51 -> -84215045 1/53 -> -1944890851 1/55 -> none 1/57 -> -1205604855 1/59 -> -1601513229 1/61 -> -1056139499 1/63 -> -1090785345 1/65 -> -1057222719 1/67 -> none 1/69 -> -1556147571 1/71 -> -483939977 1/73 -> -941362695 1/75 -> -1775253149 1/77 -> none 1/79 -> none 1/81 -> none 1/83 -> none 1/85 -> -50529027 1/87 -> none 1/89 -> -96516119 1/91 -> -755159085 1/93 -> none 1/95 -> -723362913 1/97 -> none 1/99 -> -1084587701 1/101 -> none 1/103 -> -750576809 1/105 -> -654471207 1/107 -> -1926714301 1/109 -> -630453915 1/111 -> -619094385 1/113 -> none 1/115 -> none 1/117 -> -587345955 1/119 -> none 1/121 -> none 1/123 -> -349184333 1/125 -> none 1/127 -> -270549121 1/129 -> none 1/131 -> -918008277 1/133 -> -516687795 1/135 -> -509033161 1/137 -> none 1/139 -> none 1/141 -> -852901307 1/143 -> -90104209 1/145 -> none 1/147 -> none 1/149 -> -1931294019 1/151 -> -1080852697 1/153 -> -1459727447 1/155 -> none 1/157 -> none 1/159 -> none 1/161 -> -53353631 1/163 -> none 1/165 -> none 1/167 -> -617240809 1/169 -> -76242023 1/171 -> -401868285 1/173 -> none 1/175 -> none 1/177 -> -533837743 1/179 -> -647844229 1/181 -> none 1/183 -> -1783702265 1/185 -> -371456631 1/187 -> -1584774029 1/189 -> -363595115 1/191 -> -292327617 1/193 -> -1869312191 1/195 -> -352407573 1/197 -> none 1/199 -> -280575753 1/201 -> none``` 【 design & art by Xa / Gynvael Coldwind 】 【 logo font (birdman regular) by utopiafonts / Dale Harris 】