Skip to main content
Retrocomputing

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

12
  • 3
    How do you convert something to base 3 without lookup tables or heavy math operations, before you can simply shift right a base-3 number? And maybe convert it back to something usable? Commented Dec 11, 2022 at 10:59
  • 1
    This is not an answer the question, which is "On CPUs without divide or multiply instructions like the Zilog Z80 and the MOS 6502, how could division by three be efficiently implemented?". Commented Dec 11, 2022 at 11:20
  • 2
    Shift to right is not inefficient itself. But converting 8-bit integer from base 2 to base 3 and back to base 2 is, unless you can prove otherwise. That is the missing key part in your answer. And the CPU does not work in base-3 numbers, it works in base-2 numbers, so you can only shift base-2 numbers efficiently. Commented Dec 11, 2022 at 12:15
  • 1
    You can take advantage of the fact that 4=3+1, i.e. let x=a*4+b=a*3+(a+b) then let (a+b) be the new x until x is less than 4. E.g. 255 = 63*4+3 = 63*3 + 66 = 63*3 + 16*4 + 2 = 63*3 + 16*3 + 18 = 63*3 + 16*3 + 4*4 +2 = 63*3 + 16*3 + 4*3 + 6 = 63*3 + 16*3 + 4*3 + 1*4 + 2 = 63*3 + 16*3 + 4*3 + 1*3 + 3 = 85*3. Commented Dec 11, 2022 at 13:03
  • 1
    You can easily form a recursive solution that way. I don't think I like it because it's no faster and only marginally smaller than existing answers. However it's also the only answer that can handle arbitrarily large inputs. (try adapting any of the other solutions to uint64). Commented Dec 11, 2022 at 13:28