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 <stdio.h>
#include <stdint.h>
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[1]: %lli (test: %lli =?= 1)\n", k, xn, xn*k);
xn = xn * (2 - k * xn); printf("k=%lli -> x[2]: %lli (test: %lli =?= 1)\n", k, xn, xn*k);
xn = xn * (2 - k * xn); printf("k=%lli -> x[3]: %lli (test: %lli =?= 1)\n", k, xn, xn*k);
xn = xn * (2 - k * xn); printf("k=%lli -> x[4]: %lli (test: %lli =?= 1)\n", k, xn, xn*k);
xn = xn * (2 - k * xn); printf("k=%lli -> x[5]: %lli (test: %lli =?= 1)\n", k, xn, xn*k);
xn = xn * (2 - k * xn); printf("k=%lli -> x[6]: %lli (test: %lli =?= 1)\n", k, xn, xn*k);
xn = xn * (2 - k * xn); printf("k=%lli -> x[7]: %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