Find a number's inverse using multiplication only

Question

Some taking-a-shower thinking:

Given $x$, find $1/x$ using multiplication only.

I understand these axioms

$$ n \times inv(n) = 1 $$ $$ n \div d = n \times inv(d) $$

But I couldn't think of a way to derive $1/x$ from $x$ using only multiplication.

I'm a complete math noob but if it's not possible, I'm interested in a proof that demonstrates it as fact

Answer 1

I'm assuming the numbers you are dealing with are strictly in the field $\mathbb{R}$, of real numbers with standard multiplication, $*$. A field is an algebraic structure where multiplicative inverses exist and these inverses are unique (I can provide a proof if you wish). The inverse of an element $n$ is denoted $n^{-1}$ and satisfies $n * n^{-1} = 1$. Note that $n^{-1}$ really depends on the operation which you are taking inverse of (We stick with multiplication for your sake). There is no way to explicitly compute your inverse using multiplication but the above just shows that it exists and is unique.

As requested, here is a proof for uniqueness:

Assume $m, m'$ are multiplicative inverses for $n$. Then $n*m = 1 = n*m'$. Therefore, $m = 1*m = (n*m')*m = (m'*n)*m = m'*(n*m) = m'*1 = m'$.

Answer 2

While there's no way to get an exact answer using just multiplication, it's worth noting that it's possible to generate approximate answers; in fact, this is how most CPUs have traditionally done division, by using a version of Newton's method for root-finding. Starting with a very rough approximation $x_0$ to $\frac1n$ (usually found in practice by table lookup), we can compute much better ones by setting $x_1=x_0\times(2-nx_0)$, $x_2=x_1\times(2-nx_1)$, etc; this is the same as saying that $x_{i+1} = x_i+x_i\times (1-nx_i)$ — note that if $x_i$ is close to $\frac1n$, then $1-nx_i$ will be very close to zero, so $x_{i+1}$ will be pretty close to $x_i$ and thus also pretty close to $\frac1n$. In fact, it'll be closer; if the relative error in $x_i$, that is $1-nx_i$, is $\varepsilon$, then the relative error in $x_{i+1}$ will be $1-n\times x_{i+1}$ $=1-n\times(x_i\times(2-nx_i))$ $=1-2nx_i+n^2x_i^2$ $=(1-nx_i)^2$ $=\varepsilon^2$. In other words, every iteration doubles the number of correct digits in the approximation.

You can try this yourself: suppose we want to compute $\frac17$. Well, $7$ is kind of close to $10$, so we'll start with $x_0=.1$. Now, we iterate: $$x_1=x_0(2-7x_0)=.1(2-.7)=.1\times1.3=.13$$ $$x_2 = x_1(2-7x_1)=.13(2-.91)=.13\times1.09=.1417$$ $$x_3 = x_2(2-7x_2)=.1417(2-.9919)=.1417\times1.0091=.14298947$$ And this is only about $.0001$ away from the actual value $.\overline{142857}$

Answer 3

Strictly base 10 decimals. To get $\frac 1{2^k5^m}$. e.g. to get $\frac 1{16}$ or $\frac 1{625}$ or $\frac 1{400}$.

$\frac 1{2^k5^m} * 2^k5^m = 1$ so

$\frac 1{2^k5^m} * 10^{\max(m,k)} =$

$\frac 1{2^k5^m} *(2^{\max(m,k)}5^{\max(m,k)}=$

$\frac 1{2^k5^m}*2^k5^m*2^{\max(m,k)-k}5^{\max(m,k)-m}=$

$1*2^{\max(m,k)-k}5^{\max(m,k)-m}=2^{\max(m,k)-k}5^{\max(m,k)-m}$

So

$\frac 1{2^k5^m} = $

$\frac 1{2^k5^m}*10^{\max(m,k)}*\frac 1{10^{\max(m,k)}}=$

$2^{\max(m,k)-k}5^{\max(m,k)-m}\frac 1{10^{\max(m,k)}}=$

$.2^{\max(m,k)-k}5^{\max(m,k)-m}$

Ex $\frac 1{16} = $

$\frac 1{16}*10000*\frac 1{10000}$

$\frac 1{16}*2^4*5^4*\frac 1{10000}=$

$\frac 1{16}*16*625 *\frac 1{10000}=$

$625 *\frac 1{10000}=.0625$.