[HN Gopher] Algos in Plain English - Efficient Division Without ...
___________________________________________________________________
Algos in Plain English - Efficient Division Without Mult, Div, or
Mod Operators
Author : jma353
Score : 39 points
Date : 2022-09-25 16:09 UTC (6 hours ago)
(HTM) web link (www.joeantonakakis.com)
(TXT) w3m dump (www.joeantonakakis.com)
| fsckboy wrote:
| um... I would have written this same article with the exact
| opposite slant,
|
| _Algos in Plain English - Mult, Div, and Mod make for Efficient
| Division_
|
| The "binary intuition" is that "what you already know from grade
| school about multiplying and dividing numbers _the long way_ on
| paper, by lining up and shifting columns of numbers, is even
| easier in binary because shifting _is_ multiplication and binary
| only has a 1 or a 0 in every place.
|
| I just think it's a little wrong to say "we're not mulitplying"
| when we are. And when you use Mult, Div, and Mod operators,
| that's what they do.
| sgtnoodle wrote:
| It seems a little funny to say you can't use multiplication or
| division operators, but then use shift operators to do
| multiplication and division. Also, the suggested solution uses a
| `*` in the final return...
|
| It seems like you could instead use addition of a value with
| itself for the multiplication by 2, and it seems like there isn't
| any inherent need to divide by 2.
|
| Here's my submission (set to expire after a month).
| https://pastebin.com/mgvGakLL
| onos wrote:
| Here's another as valid as given in the post.
|
| A/ b = exp(log(a) - log(b))
|
| No multiplication or division!
| whatshisface wrote:
| I think the implied context is "you're only allowed to use
| instructions that involve simpler circuitry than
| multiplication or division." Otherwise there's no point in
| asking the question.
| bogomipz wrote:
| This was a great read! I hope you keep up the "Algos in Plain
| English" series. Its' a great idea. I also enjoyed the one on
| KMP. I also thought that was well written.
| marginalia_nu wrote:
| I came up with a cute algorithm for arbitrary division with
| repeated shifts when working on one of my earlier projects, which
| was an emulator for a trinary computer (where obviously dividing
| by 3 was a thing of import).
|
| A recursive expression is derived like this 1
| 1 b-a --- - --- = ---- a b a b
| 1 1 (b-a) 1 --- = --- + ----- --- a b
| b a
|
| If you select 1/b to be nearby a power of your base, this
| recursive relationship can be expanded until you get adequate
| precision.
|
| e.g. to express 1/7 in terms of divisions by 8 (i.e. binary
| shifts by 3) 1 1 1 - = - ( 1 +
| ---) 7 8 7 1 1 1 1
| - = - + --- (1 + ---) 7 8 64 7 1 1
| 1 1 1 - = - + --- + --- ( 1 + --- ) 7 8
| 64 512 7
|
| So you get v/7 = v>>3 + v>>6 + v>>9 + v>>12 + ... (mind the
| carry). You sometimes end up needing to do some multiplication
| too but usually b can be chosen to make the problem a series of
| trivial operations.
|
| Good expression to be able to derive in case you need to rebuild
| humanity from a box of nand gates.
|
| Thanks for coming to my TED talk.
| jepler wrote:
| You might remove the use of multiplication at the end:
| return max(min(answer * sign, MAX_INT), MIN_INT)
___________________________________________________________________
(page generated 2022-09-25 23:01 UTC)