5

I need to perform a division operation using only addition and multiplication. I can't use substraction. Is it somehow possible to do that with only these two operations?

StuntHacks
  • 151
  • 4
    What the heck does this mean? How about multiplying by the reciprocal? The rules of this "game" are definitely not well-defined. – Franklin Pezzuti Dyer Nov 10 '18 at 16:56
  • @Frpzzd Sorry, if my question isn't that well defined. Basically, all I can do is adding and/or multiplaying two numbers. I can't multiply by the reciprocal since for that, I'd need to perform division first as well. – StuntHacks Nov 10 '18 at 16:58
  • What are your two numbers? – Franklin Pezzuti Dyer Nov 10 '18 at 16:59
  • Are we only working with integers ? – krirkrirk Nov 10 '18 at 16:59
  • @Frpzzd Basically, any two numbers. – StuntHacks Nov 10 '18 at 17:00
  • @krirkrirk No, sadly not. By the nature of the system I'm working with, we have to deal with floating point numbers. – StuntHacks Nov 10 '18 at 17:00
  • 2
    To compute $x = 1/p$, you can start with an initial guess $x = x_0$, and then compute the successive approximations $x_n$ using the recursion: $$x_{n+1} = 2 x_n - p x_n^2$$ – Count Iblis Nov 10 '18 at 17:07
  • @CountIblis Thank you very much! – StuntHacks Nov 10 '18 at 17:12
  • @CountIblis: But that uses subtraction, which the question bars, doesn't it? – Brian Tung Nov 10 '18 at 17:53
  • @StuntHacks: You'll have to be even clearer about your question, about what operations are permitted. Lucozade's answer, for example, uses digit-wise complements, which might be permissible to you, or might not. – Brian Tung Nov 10 '18 at 17:56
  • "But that uses subtraction" Subtraction is merely addition by the additive inverse. If multiplication is allowed and if $(-1)$ is a valid number, then $a - b = a + (-1)\times b$ can be expressed using only addition and multiplication. – JMoravitz Nov 10 '18 at 18:43
  • @JMoravitz: But he says he can't use subtraction; there must be something that distinguishes it in his problem. – Brian Tung Nov 10 '18 at 18:57
  • Yes, sadly the system I'm working with doesn't support negative numbers (in this case). I should have specified that, probably. – StuntHacks Nov 10 '18 at 19:03

2 Answers2

1

If you can do comparisons, then you can manage this to an arbitrary precision.

Let the two numbers be $a$ and $b$, and you are trying to compute $b \div a$. If $a = 0$, the division is illegal, and you are done. If $b = 0$, the quotient is $0$, and you are done.

Otherwise, count up how many times you can add $a$ to itself before reaching or surpassing $b$. Make sure you keep track of the running sums. If you reach $b$ exactly, this is the integer quotient $q$ exactly, and you are done.

Otherwise, one less than the count is $q$, the integer portion of the quotient, and the next-to-last sum was was $qa$. Now multiply both it and $b$ by $10$, so you now are comparing $10qa$ and $10b$. Again, add $a$ to the former until you reach or surpass $10b$. If you reach $10b$ exactly, then the count is $r_1$, the first and last decimal digit of the quotient, and you are done.

Otherwise, $r_1$ is one less than the count. If you kept track of your running sums, the previous sum will be $(10q+r_1)a$. Multiply both this and $10b$ by $10$, so now you are comparing $(100q+10r_1)a$ and $100b$. Again, add $a$ to the former until you reach or surpass $100b$, which will allow you to determine $r_2$, the second digit of the decimal portion of the quotient. I trust you can take it from here.

Example. Let $a = 4$ and $b = 19$. We can add $a = 4$ to itself $5$ times to surpass $b = 19$, so one less than that is $q = 4$, the integer portion of the quotient.

The previous sum was $qa = 16$. Multiply both this and $b$ by $10$ to get $10qa = 160$ and $10b = 190$. We can add $a = 4$ to $10qa = 160$ a total of $8$ times before surpassing $10b = 190$, so one less than that is $r_1 = 7$, the first digit of the decimal portion of the quotient.

The previous sum was $10qa+r_1a = 188$, so we multiply both this and $190$ by $10$ to get $1880$ and $1900$. We can add $a = 4$ a total of $5$ times to the $1880$ to reach $1900$ exactly, so $r_2 = 5$ is the second and final digit of the decimal portion of the quotient.

Brian Tung
  • 34,160
  • If you're doing this on a computer, you may wish to do this is binary, rather than decimal. This simplifies the matter of making a count, since (except for the integer portion) it will be either $0$ or $1$. – Brian Tung Nov 10 '18 at 18:18
  • It looks like you have a typo, having written $b\div a$ instead of $a\div b$ – JMoravitz Nov 10 '18 at 18:42
  • @JMoravitz: Are you sure? I don't think so. I'm adding $a$ to get $b$; doesn't that yield $b \div a$? – Brian Tung Nov 10 '18 at 18:57
  • The line in question, $b\div a$ if $b$ is zero is illegal, and if $a$ is zero the quotient is zero. What follows does seem like a description of $b\div a$ but surely $b\div a$ is illegal when a is zero instead, – JMoravitz Nov 10 '18 at 19:02
  • @JMoravitz: Ahh yes, that line is reversed, thanks. – Brian Tung Nov 10 '18 at 23:30
0

A long division involves multiplication and subtraction at each stage, so you only need to consider converting an addition into a subtraction. You can do this (in the decimal number system) by taking the 10's complement of the subtrahend, which you then add and ignore any carry-out (similar to the subtraction algorithm for binary numbers).

Example for $23 - 15 = 08$: The $9$'s complement of $15$ is $(9-1)(9-5) = 84$, hence the $10$'s complement is $84+1=85$. Thus, $23+85=108$. Ignoring the carry-out leading $1$ gives $08$.

NB: it's debatable whether taking the complement is a subtraction operation or not. As there are only $10$ digits, it can be done using a look-up table instead of performing an actual mathematical operation.

Lucozade
  • 733