Hi there,
as you can see from the subject, I wanted to get to know division using multiplication. I know the general idea and I get why it has to work, but I'm not able to understand the mathematical background used to implement the algorithms in a compiler that generate code that uses imul and a few shifts instead of idiv which is a lot slower. I already found this paper:
https://gmplib.org/~tege/divcnst-pldi94.pdf , but can't get why the part explainded at column 2 of page 3 starting with "Setting n=q*d-1" works. I already asked my teacher, but he's kind of slow since he has work to do, so I'll ask the community here. Anyway: does anyone have some ideas/techniques to get the (invariant) integer by which a code that will look rather cryptic since using magic numbers and shifts divides? This is something I can't get around and almost every program uses division, so it's a pity not to be able to reverse-engineer it. Any help?
Thanks, TheWormKill
