Bin-BCD: Not Using Double Dabble

[auztin3]

Hey guys, I have a question that's been bugging me for a pretty long time and I can't figure out the answer . As for a background, I was thinking about Bin-BCD, and found dividing by ten/hundred and finding the remainder, would work perfectly. Division by ten was easy by bit shifting, but you had multiply that number back by ten, and subtract from the original value to find the remainder.

Example:

97/10
9-tens
9x10 = 90
97-90
7- ones

That's the longer way of doing this taking around 14 ticks. That brings me back to the question, is there an easier way to find the remainder? Say, how could you know the remainder of 16/10 would be 6 without actually dividing or doing the long multiplication back? Thanks

[Killerbunny]

x/10 = (x/2)/5) so your rest is equal to (x/2)mod 5 = R/2 where (R/2 < 5)
or X mod 10 = R where (R < 10 )
R = rest
Mod = moduler arithmatic
I am not sure if this helps or not but if you want help search for modular arithmetic.
Edit-
So I had an idea that might be noteworthy. As we know
R=1, 2, 3, 4, 5, 6, 7, 8, 9
If X mod 2 = 1
Then R mod 2 = 1
If R mod 2 = 1
Then R = 1,3,5,7,9
Else R = 0,2,4,6,8
Meaning we can reduce our search down to 5 just by checking the one bit.
I think it is possible to reduce this number even further, but I'm not exactly sure how. I think it has to do with mod 4 or 5.

[Killerbunny]

If you look at the binary numbers numbers in decimal we see it follows a simple pattern in the one bits, witch are the ones you care about when performing X mod 10 . The pattern goes like this.
(1) 2 4 8 6 2 4 8 6
We add the corresponding values together, and do mod 10 on this value. In all I think it can be performed in 11 ticks if you use signal stregth to add these numbers. But maybe you can speed it up a bit more.

-Edit
I found a way to speed things up by using the formula X/2 mod 5 = R/2
So in our case X is equal to one of the values in the pattern ( (1) 2 4 8 6 ) by dividing eatch value by two ( so (1) 1 2 4 3) we can fit all four in one redstone line, and when all the numbers fit in one line we can easly performe mod 5.

To convert back we just multiply by two and add 1 if the one bit is on. In all I think we get a anwser in ca 8 or 9 ish ticks.