Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Scaling 64 bit integers

, 22 Feb 2005
An article on scaling 64 bit integers using extended precision integer arithmetic.
muldiv64_demo.zip
muldiv64_src.zip
MulDiv64
Release
MulDiv64.lib
TestMulDiv64
Release
TestMulDiv64.exe
<!--------------------------------------------------------------------------->
<!--                           INTRODUCTION                                

 The Code Project article submission template (HTML version)

Using this template will help us post your article sooner. To use, just 
follow the 3 easy steps below:
 
     1. Fill in the article description details
     2. Add links to your images and downloads
     3. Include the main article text

That's all there is to it! All formatting will be done by our submission
scripts and style sheets. 

-->
<!--------------------------------------------------------------------------->
<!--                        IGNORE THIS SECTION                            --><html><head>
		<title>The Code Project</title>
		<STYLE> BODY, P, TD { font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10pt }
	H2,H3,H4,H5 { color: #ff9900; font-weight: bold; }
	H2 { font-size: 13pt; }
	H3 { font-size: 12pt; }
	H4 { font-size: 10pt; color: black; }
	PRE { BACKGROUND-COLOR: #FBEDBB; FONT-FAMILY: "Courier New", Courier, mono; WHITE-SPACE: pre; }
	CODE { COLOR: #990000; FONT-FAMILY: "Courier New", Courier, mono; }
	</STYLE>
		<link href="http://www.codeproject.com/styles/global.css" type="text/css" rel="stylesheet"></head>
	<body bgColor="#ffffff" color="#000000">
		<!--------------------------------------------------------------------------->
		<!-------------------------------     STEP 1      --------------------------->
		<!--  Fill in the details (CodeProject will reformat this section for you) --><pre>Title:       Scaling 64 bit integers
Author:      Richard van der Wal&nbsp;
Email:       <A href="mailto:R.vdWal@xs4all.nlEnvironment" >R.vdWal@xs4all.nl</A>
Environment: VC++ 5.0-6.0-7.0, NT4.0, Win95/98, W2K, WinXP Keywords: Library, Assembly, Win32 
Level:       Intermediate
Description: An article on scaling 64 bit integers using extended precision integer arithmetic
Section      Miscellaneous
SubSection   General
</pre>
		<!-------------------------------     STEP 2      --------------------------->
		<!--  Include download and sample image information.                       -->
		<ul class="download">
			<li>
				<A href="Article_demo.zip">Download demo project - XXX Kb </A>
			<li>
				<A href="Article_src.zip">Download source - XXX Kb</A>
			</li>
		</ul>
		<!--
		<p><img src="Article.gif" alt="Sample Image - maximum width is 600 pixels" width="400" height="200"></p>
-->
		<!-------------------------------     STEP 3      --------------------------->
		<!--  Add the article text. Please use simple formatting (<h2>, <p> etc)   -->
		<h2>Introduction</h2>
		<p>
		Ever needed to scale 64 bit integers? I did when I was building a time tracking 
		Kalman Filter. I decided to keep track of time as a 64 bit integer just as the 
		.NET framework does. The big advantage of using the 64 bit integer is that you 
		can keep time up to 100 nanosec. accurate and keep that accuracy after 2012. 
		That is approximately the date after which you can no longer store seconds 
		since 1980 in a double with microsecond accuracy. Another advantage is the easy 
		exchange of times with .NET.
		<P>
		So I coded al the time keeping using __int64. This all went&nbsp;pretty well 
		since the VS C++ compiler supports most arithmetic operations with __int64. You 
		can add, subtract, multiply and divide, but all with the limitation that the 
		result has to fit in a __int64. The problem arose when I wanted to scale a time 
		value. The general idea of scaling is to express the scale factor as&nbsp;the 
		quotient of a numerator and a denominator, then first multiply with&nbsp;the 
		numerator&nbsp;and then divide by the denominator. You can�t use a separate 
		multiplication and division for that since the intermediate result of the 
		multiplication can be too large to fit a __int64. This problem used to exist in 
		the 32 bit world when 64 bit integers were not yet supported by compilers. 
		That�s why Windows provides a MulDiv function that does the multiplication and 
		the division in one call, keeping track of the 64 bit intermediate result. The 
		32 bit processors for the PC all support extended 32 bit divisions. 
		Unfortunately&nbsp;the OS&nbsp;doesn�t provide us with a function to do the 
		same thing with 64 bit integers. This is probably because the div instruction 
		on today�s processors doesn�t support extended 64 divisions, yet.
		<P>
		The main problem lies with the 128 bit intermediate result that is needed to do 
		a full 64 bit MulDiv(). After spending many hours on the web to find a 
		pre-cooked solution I found a few references to the gnu MulDiv64 which scales a 
		64 bit integer with two 32 bit values and the book �The Art of Assembly 
		Programming� by Randall Hyde. The 64*32/32 MulDiv would do the trick but didn't 
		realy satisfy my search for a full 64*64/64 MulDiv that would allow me to use 
		only __int64. Thus I turned to&nbsp;Randall's book.&nbsp;This contained a 
		section on Extended Precision integer arithmetic which was exactly what I 
		needed. I implemented the methods described there in a small C++ library called 
		MulDiv64. This way you don't have to go through all the nitty gritty of 
		puzzling the pieces of the book together and the inline assembly programming.
		<P>The MulDiv64 library provides two functions:<BR>
			<code>__int64 _stdcall MulDiv64(__int64 operant, __int64 multiplier, __int64 
				divider);</code>
			<BR>
			<code>__int64 _stdcall MulShr64(__int64 operant, __int64 multiplier, unsigned char 
				rshift);</code>
		</P>
		<P>In situations where the divider can be kept constant at a power of 2 then the 
			division can be implemented using a right shift. This results in a much faster 
			scaling because the full 128 bit division is somewhat slow due to the lack of 
			hardware support.
		</P>
		<h2>Using the code</h2>
		<P>The library is implemented as a C++ static library. This way you avoid DLL or 
			COM overhead in your calculations. Most functionality is written using inline 
			assembly, except for the ABS() operations which the compiler can do efficiently 
			itself. I tried to catch special conditions where processor support can be used 
			to speed up the calculation. For example, when the divider is small enough to 
			fit in a DWORD, the division can be done in four chunks instead of bit by bit. 
			The result is always a 128 bit value but both functions clip the result to 64 
			bit because that is usually what you�re after.&nbsp;</P>
		<P>Include the library MulDiv64.lib in the Additional Dependencies for your linker 
			input. This can be found in the project properties dialog.&nbsp;Don't forget to 
			include the header file as well.</P>
		<p>An example for using the library:
		</p>
		<pre>#include "MulDiv64.h"

int _tmain(int argc, _TCHAR* argv[])
{
	__int64 r = 0;
	__int64 a = 0xaaaaaaaaaaaaaaaa;
	__int64 b = 0x5555555555555555;
	__int64 c = 0x1000000000000000;	// = 1 shl 60
	char s = 60;
	
	// This will return an incorrect result
	r = a * b / c;
	
	// This will return the correct result
	r = MulDiv64(a, b, c);
	
	// Because dividing by c can be expressed as a right shift
	// we can obtain the correct scaling faster with:
	r = MulShr64(a, b, s);
	
	return 0;
}
</pre>
		<p>
		Of course, the code could be imported in many other ways. For instance it might 
		be convenient to compile the library to a DLL or COM object. But usage this way 
		will lead to significant performance loss.
		<P>
		You will see that the included test program is a little more verbose so that it 
		can be run from the command line.
		<P>
			&nbsp;
			<h2>
				<!-------------------------------    That's it!   ---------------------------></h2>
	</body>
</html>

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

R. van der Wal
Software Developer (Senior)
Netherlands Netherlands
Richard van der Wal is a Software Development Engineer at Fugro Intersite B.V. and a IT student at the Open University in the Netherlands. He holds a bachelors in mechanical engineering and had many years of experience in industrial automation before he started his job at Intersite. His current activities focus on software design and system design for real-time data processing in the offshore industry.

| Advertise | Privacy | Mobile
Web01 | 2.8.140821.2 | Last Updated 23 Feb 2005
Article Copyright 2005 by R. van der Wal
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid