|
#REDIRECT [[Fixed-point arithmetic#Binary scaling]] {{R from merge}} {{R to section}} {{R with possibilities}}
{{More citations needed|date=December 2009}}
{{Use dmy dates|date=August 2019|cs1-dates=y}}
'''Binary scaling''' is a [[computer programming]] technique used typically in embedded [[C (programming language)|C]], [[Digital signal processing|DSP]] and [[assembly language|assembler]] programs to implement non-integer operations by using the native [[integer]] arithmetic of the processor.
==Overview==
A representation of a value using binary scaling is more precise than a floating-point representation occupying the same number of bits, but typically represents values of a more limited range, therefore more easily leading to [[arithmetic overflow]] during computation. Implementation of operations using integer arithmetic instructions is often (but not always) faster than the corresponding floating-point instructions.
A position for the 'binary point' is chosen for each variable to be represented, and binary shifts associated with arithmetic operations are adjusted accordingly. The binary scaling corresponds in [[Q (number format)]] to the first digit, i.e. Q1.15 is a 16 bit integer scaled with one bit as integer and fifteen as fractional. A Bscal 1 or Q1.15 number would represent approximately 1.999 to −2.0.
To give an example, a common way to use [[arbitrary-precision arithmetic|integer arithmetic]] to simulate floating point, using 32-bit numbers, is to multiply the coefficients by 65536.
Using [[binary scientific notation]], this will place the binary point at B16. That is to say, the most significant 16 bits represent the integer part the remainder are represent the fractional part. This means, as a signed two's complement integer B16 number can hold a highest value of <math> \approx 32767.9999847 </math> and a lowest value of −32768.0. Put another way, the B number, is the number of integer bits used to represent the number which defines its value range. Remaining low bits (i.e. the non-integer bits) are used to store fractional quantities and supply more accuracy.
For instance, to represent 1.2 and 5.6 as B16 one multiplies them by 2<sup>16</sup>, giving 78643 and 367001.
Multiplying these together gives
28862059643
To convert it back to B16, divide it by 2<sup>16</sup>.
This gives 440400B16, which when converted back to a floating point number (by dividing again by 2<sup>16</sup>, but holding the result as floating point) gives 6.71999. The correct result is 6.72.
==Re-scaling after multiplication==
The example above for a B16 multiplication is a simplified example. Re-scaling depends on both the B scale value and the word size. B16 is often used in 32 bit systems because it works simply by multiplying and dividing by 65536 (or shifting 16 bits).
Consider the Binary Point in a signed 32 bit word thus:
0 1 2 3 4 5 6 7 8 9
S X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
where S is the sign bit and X are the other bits.
Placing the binary point at
* 0 gives a range of −1.0 to 0.999999.
* 1 gives a range of −2.0 to 1.999999
* 2 gives a range of −4.0 to 3.999999 and so on.
When using different B scalings and/or word sizes the complete B scaling conversion formula must be used.
Consider a 32 bit word size, and two variables, one with a B scaling of 2 and the other with a scaling of 4.
1.4 @ B2 is 1.4 * (2 ^ (wordsize-2-1)) == 1.4 * 2 ^ 29 == 0x2CCCCCCD
Note that here the 1.4 values is very well represented with 30 fraction bits. A 32 bit [[IEEE floating-point standard|floating-point number]] has 23 bits to store the fraction in. This is why B scaling is always more accurate than floating point of the same word size. This is especially useful in [[integrator]]s or repeated summing of small quantities where [[rounding error]] can be a subtle but very dangerous problem when using floating point.
Now a larger number 15.2 at B4.
15.2 @ B4 is 15.2 * (2 ^ (wordsize-4-1)) == 15.2 * 2 ^ 27 == 0x7999999A
The number of bits to store the fraction is 28 bits.
Multiplying these 32 bit numbers give the 64 bit result {{mono|0x1547AE14A51EB852}}
This result is in B7 in a 64 bit word. Shifting it down by 32 bits gives the result in B7 in 32 bits.
0x1547AE14
To convert back to floating point, divide this by {{code|1=(2^(wordsize-7-1)) == 21.2800000099}}
Various scalings may be used. B0 for instance can be used to represent any number between −1 and 0.999999999.
=={{anchor|BAM}}Binary angles==
<!-- Binary angle (computing), Binary Angular Measurement System, and Binary radian redirect here -->
[[Image:Binary angles.svg|360px|thumb|Binary scaling (B0) Representation of angles. <span style="color:black">Black</span> is traditional degrees representation, <span style="color:green">green</span> is BAM as a real number and <span style="color:red">red</span> is [[hexadecimal]] 32-bit representation of the BAM.]]
Binary angles are mapped using B0, with 0 as 0 degrees, 0.5 as 90° (or <math>\frac{\pi}{2}</math>), −1.0 or 0.9999999 as 180° (or π) and −0.5 as 270° (or <math>\frac{3\pi}{2}</math>). When these binary angles are added using normal [[two's complement]] mathematics, the rotation of the angles is correct, even when crossing the sign boundary (this of course does away with checks for angle ≥ 360° when handling normal degrees<ref name="Hargreaves_2010"/>
The terms '''binary angular measurement''' ('''BAM''')<ref name="ship"/> and '''binary angular measurement system''' ('''BAMS''')<ref name="BAMS"/> as well as '''brads''' ('''binary radians''' or '''binary degree''') refer to implementations of binary angles. They find use in robotics, navigation,<ref name="LaPlante_2004"/> computer games,<ref name="Sanglard_1993"/> and digital sensors.<ref name="Parallax_2005"/>
No matter what bit-pattern is stored in a binary angle, when it is multiplied by 180° (or π) using standard signed [[fixed-point arithmetic]], the result is always a valid angle in the range of −180° [[degree (angle)|degree]]s (−π [[radian]]s) to +180° degrees (+π radians).
In some cases, it is convenient to use unsigned multiplication (rather than signed multiplication) on a binary angle, which gives the correct angle in the range of 0 to +360° degrees (+2π radians or +1 [[turn (geometry)|turn]]).
Compared to storing angles in a binary angle format, storing angles in any other format inevitably results in some bit patterns giving "angles" outside that range, requiring extra steps to [[trigonometric functions#Computation|range-reduce]] the value to the desired range, or results in some bit patterns that are not valid angles at all ([[NaN]]), or both.
==Application of binary scaling techniques==
Binary scaling techniques were used in the 1970s and 1980s for real-time computing that was mathematically intensive, such as [[flight simulation]] and in [[Nuclear Power Plant]] control algorithms since the late 1960s. The code was often commented with the binary scalings of the intermediate results of equations.
Binary scaling is still used in many [[digital signal processing|DSP]] applications and custom made microprocessors are usually based on binary scaling techniques.
Binary scaling is currently used in the [[Discrete cosine transform|DCT]] used to compress [[JPEG]] images in utilities such as [[GIMP]].
Although floating point has taken over to a large degree, where speed and extra accuracy are required, binary scaling works on simpler hardware and is more accurate when the range of values is known in advance.{{Clarify|date=March 2016|post-text=→[[Talk:Binary scaling#Comparison with Floating Point|talk]]}}
==See also==
* [[Libfixmath]] – a library written in C for fixed-point math
* [[Q (number format)]]
* [[Minifloat]]
* [[Block floating-point scaling]]
* [[Modulo operation]]
==References==
{{Reflist|refs=
<ref name="Hargreaves_2010">{{cite web |title=Angles, integers, and modulo arithmetic |author-first=Shawn |author-last=Hargreaves |author-link=:pl:Shawn Hargreaves |publisher=blogs.msdn.com |url=http://blogs.msdn.com/shawnhar/archive/2010/01/04/angles-integers-and-modulo-arithmetic.aspx |access-date=2019-08-05 |url-status=live |archive-url=https://web.archive.org/web/20190630223817/http://www.shawnhargreaves.com/blogindex.html |archive-date=2019-06-03}}</ref>
<ref name="ship">{{cite web |title=Binary angular measurement |url=http://www.tpub.com/content/fc/14100/css/14100_314.htm |archive-url=https://web.archive.org/web/20091221160257/http://www.tpub.com/content/fc/14100/css/14100_314.htm |archive-date=2009-12-21}}</ref>
<ref name="BAMS">{{cite web |title=Binary Angular Measurement System |work=acronyms.thefreedictionary |url=http://acronyms.thefreedictionary.com/Binary+Angular+Measurement+System}}</ref>
<ref name="LaPlante_2004">{{cite book |title=Real-Time Systems Design and Analysis |chapter=Chapter 7.5.3, Binary Angular Measure |author-first=Phillip A. |author-last=LaPlante |date=2004 |website=www.globalspec.com |chapter-url=http://www.globalspec.com/reference/14722/160210/Chapter-7-5-3-Binary-Angular-Measure}}</ref>
<ref name="Sanglard_1993">{{cite web |title=Doom 1993 code review - Section "Walls" |author-first=Fabien |author-last=Sanglard |date=2010-01-13 |website=fabiensanglard.net |url=http://fabiensanglard.net/doomIphone/doomClassicRenderer.php}}</ref>
<ref name="Parallax_2005">{{cite web |title=Hitachi HM55B Compass Module (#29123) |series=Parallax Digital Compass Sensor (#29123) |publisher=[[Parallax, Inc. (company)|Parallax, Inc.]] |date=May 2005 |website=www.hobbyengineering.com |via=www.parallax.com |url=http://www.hobbyengineering.com/specs/PX-29123.pdf |url-status=dead |archive-url=https://web.archive.org/web/20110711172521/http://www.hobbyengineering.com/specs/PX-29123.pdf |archive-date=2011-07-11}}</ref>
}}
{{DEFAULTSORT:Binary Scaling}}
[[Category:Binary arithmetic|Scaling]]
| 