Some Suggested Code

In This Earlier Posting, I had written at first some observations about Bluetooth-pairing, but then branched out on the subject, of whether a Diffie-Hellman Key Exchange could be easier to compute, if it was somehow simplified into using a 32-bit modulus. Obviously, my assumption was that a 64-bit by 32-bit divide instruction would be cheap on the CPU, while arbitrary-precision integer operations are relatively expensive, and actually cause some observable lag on CPUs which I’ve used.

And so, because I don’t only want to present theory in a form that some people may not be able to visualize, what I did next was to write a C++ program, that actually only uses C, that assumes the user only has a 32-bit CPU, and yet that performs a 64-bit by 64-bit division.

This has now been tested and verified.

One problem in writing this code is the fact that, depending on whether the divisor, which is formatted as a 64-bit field, contains an actual 64-bit, 32-bit, 24-bit, or 16-bit value, a different procedure needs to be selected, and even this fixed-precision format cannot assume that the bits are always positioned in the correct place.

I invite people to look at this sample-code:

http://dirkmittler.homeip.net/text/divide64.cpp

(Update 06/10/2018, 23h30 : )

I needed to correct mistakes which I made in the same piece of code. However, I presently know the code to be correct.

Just to test my premises, I’m going to assume that the following division is to be carried out, erroneously as a simple division, but assuming a word-size of 32 bits:

 


    0x FFFF FFFF FF00 0000
/   0x 0000 0000 8000 0000

 

What we would find, is that the following value will act as the temporary quotient:

 


    0x FFFF FFFF

 

But, multiplying that by the divisor and subtracting, would yield a temporary remainder, still greater than the divisor. Thus, my algorithm would next subtract the divisor from that one more time, still yielding too great a remainder, and would also add (1) to the quotient, resulting in an overflow. Thus, the approach is not suited if the quotient is needed, but a derived approach might be suited if only the remainder / modulus is needed. And, the correct answer would be:

 


Q:  0x 0000 0001 FFFF FFFF
R:  0x 0000 0000 7F00 0000

 

Dirk

 

Print Friendly, PDF & Email

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

This site uses Akismet to reduce spam. Learn how your comment data is processed.