Active questions tagged floating-point - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-21T21:40:08Z https://cs.stackexchange.com/feeds/tag/floating-point https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/102973 0 Floating point precision from rearranging equation Paradox https://cs.stackexchange.com/users/36000 2019-01-17T04:01:53Z 2019-09-14T21:23:32Z <p>When I run <span class="math-container">$x^2 - y^2$</span> with x=8.8888888888 and y=9.9999999999 in python, I get the following result:</p> <pre><code>&gt;&gt;&gt; 8.8888888888**2 - 9.9999999999**2 -20.9876543205679 </code></pre> <p>However, if I rearrange it to <span class="math-container">$(x-y)(x+y)$</span> with the same x and y values, I get:</p> <pre><code>&gt;&gt;&gt; (8.8888888888 - 9.9999999999) * (8.8888888888 + 9.9999999999) -20.987654320567895 </code></pre> <p>It seems that the two equations, though logically equivalent, give varying amounts of floating point precision by a difference of 2 digits. What could be causing this?</p> https://cs.stackexchange.com/q/114746 0 Is Decimal (correctly-rounded arbitrary precision decimal floating point arithmetic) fixed-point, floating-point or something else? Louis Ng https://cs.stackexchange.com/users/109414 2019-09-14T14:57:52Z 2019-09-14T14:57:52Z <p>The Decimal data type I am referring to is GNU MPFR(<a href="https://en.wikipedia.org/wiki/GNU_MPFR" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/GNU_MPFR</a>), or libmpdec (<a href="http://www.bytereef.org/mpdecimal/doc/libmpdec/index.html" rel="nofollow noreferrer">http://www.bytereef.org/mpdecimal/doc/libmpdec/index.html</a>).</p> <p>I have been searching for information about decimal for days and learned that you can use fixed-point (int + scaling factor) to represent a non-int real number, but I have looked into the above two libraries, which doesn't look like fixed-point. Instead, they refer to the implementation as (correctly-rounded arbitrary precision decimal floating point arithmetic).</p> <p>The information online is very limited (or there are something obvious I have missed).</p> <p>I would like to know more.</p> https://cs.stackexchange.com/q/114723 2 Smallest integer i stored as a float such that i+1=i user185887 https://cs.stackexchange.com/users/109523 2019-09-13T17:00:20Z 2019-09-14T05:37:11Z <p>So I had an assignment which asked me to find the smallest integer <span class="math-container">$i$</span> which when represented as a float is such that <span class="math-container">$i+1=i$</span></p> <p>My approach- By making a simple C++ program , we get <span class="math-container">$i=16777216$</span> or <span class="math-container">$i=2^{24}$</span> But if we want to do that theoretically, I am unable to arrive at this number.</p> <p>So a float is 32 bit variable and the first bit represents sign of mantissa and the next 23 bits represent the number in Mantissa. The next bit represents sign of the exponent and the following 7 bits represent the value of exponent.</p> <p>Now consider <span class="math-container">$2^{23}$</span>. In Binary, it is represented as <span class="math-container">$1000,0000,0000,0000,0000,0000$</span> (the comma's are just to make things readable). Now if we add <span class="math-container">$1$</span> to it, it becomes <span class="math-container">$1000,0000,0000,0000,0000,0001$</span></p> <p>Now we store these numbers as float in C++. Both the numbers <span class="math-container">$2^{23}$</span> and <span class="math-container">$2^{23}+1$</span> are stored as <span class="math-container">$0100,0000,0000,0000,0000,0000,00010111$</span> (the 1 in the end has to be scrapped in order to fit the number in 24 bits). So both of them are essentially the same for the computer.</p> <p>But why does the computer give me answer as <span class="math-container">$2^{24}$</span>?</p> <p>The code that I used</p> <pre><code>#include&lt;iostream&gt; using namespace std; int main(){ float i=1; while(1&lt;2) { if(i+1==i) {cout &lt;&lt; fixed &lt;&lt; i &lt;&lt; endl; break;} i=i+1; } } </code></pre> https://cs.stackexchange.com/q/114639 2 Why multiplying float number by multiple of 10 seems to preserve better precision? Louis Ng https://cs.stackexchange.com/users/109414 2019-09-11T13:59:23Z 2019-09-11T15:08:30Z <p>It is famous that for float numbers:</p> <pre><code>.1 + .2 != .3 </code></pre> <p>but</p> <pre><code>1+2=3 </code></pre> <p>It seems that multiplying floats by 10 allows you to preserve more precision. To further illustrate the case, we can do this in python:</p> <pre><code>sum([3000000000.001]*300) #900000000000.2957 sum([3000000000.001 * 1000]*300) / 1000 #900000000000.3 </code></pre> <p>By multiplying each element in the list by 1000 and divide the sum of the list by 1000, I can get the "correct" answer. I am wondering: 1) why it's the case. 2) Will this always work, and 3) At what magnitude, will this method backfire, if it will.</p> https://cs.stackexchange.com/q/113435 1 How does a computer compute negative(-) and positive(+) Infinity? ReturnZero https://cs.stackexchange.com/users/108278 2019-09-05T05:39:40Z 2019-09-05T23:28:48Z <p>If we divide (1.0/0.0) we will get +Infinity and if we divide (-1.0/0.0) we will get -Infinity. </p> <p>How does a computer calculate this value internally?</p> https://cs.stackexchange.com/q/113133 1 Can we represent $\sqrt{2}$ exactly even with infinite bits in mantissa [closed] Zulu Raman https://cs.stackexchange.com/users/108924 2019-08-27T14:33:31Z 2019-08-27T14:41:56Z <p>Can we represent <span class="math-container">$\sqrt{2}$</span> exactly even with infinite bits in mantissa in floating point notation or otherwise. We actually have to prove this is not possible. But why can't we if we have infinite bits? Infinite bits means the binary representation of the mantissa can be indefinitely large. The mantissa is in IEEE 754 32 bit format and in a hypothetical world where we don't have a bound on the number of bits which can be used to represent it.</p> https://cs.stackexchange.com/q/97995 0 Using a 16-bit 2,s Complement normalised floating-point representation; 10-bit fractional mantissa and a 6-bit integer exponent: express 2.171875 garyfrompokemans https://cs.stackexchange.com/users/94407 2018-10-01T10:45:06Z 2019-08-27T13:02:30Z <p>So far I know how to normalize when you are given, say: 1111010010 Mantissa, and 000100 exponent and are told that it's a positive number:</p> <pre><code>1.111010010 and the exponent value is 4 move point 3 to the right: 1111.010010 subtract exponent by 3 = 1; 000001 replace extra binary digits behind sign bit with trailing 0s 1.010010000 so 1.010010000 , 000001 is the normalized form. </code></pre> <p>Now how do I express 2.171875 under the same representation? I started by converting it to binary: 10.0010110 but how do I represent that as 10-bits 2'C Mantissa and 6-bits exponent to begin with? Or am I completely lost?</p> https://cs.stackexchange.com/q/92467 0 Computing the error bound of floating-point expression plasmacel https://cs.stackexchange.com/users/55291 2018-05-29T11:54:16Z 2019-08-23T00:02:10Z <p>How should I compute the maximum absolute and relative error of the following IEEE-754 floating-point expression?</p> <pre><code>a.y + (x - a.x) * ((b.y - a.y) / (b.x - a.x)) </code></pre> <p>Also, we assume, that</p> <ul> <li>the optimizer leaves the expression in the specified form</li> <li>the default rounding mode (round to nearest even)</li> </ul> https://cs.stackexchange.com/q/98965 0 How to compute relative error for the rounding of floating point numbers when the rounded number is 0? tmaric https://cs.stackexchange.com/users/95406 2018-10-23T12:28:41Z 2019-08-19T20:01:40Z <p>I have asked this question on Stack Overflow, I am asking it here in the hope to get more traction.</p> <p>The relative rounding error for a floating point number x is defined as </p> <p><span class="math-container">$e_r = |\frac{(round(x) - x)}{x}| = |\frac{round(x)}{x} - 1|$</span> (1)</p> <p>Assuming that the rounding to nearest mode is used for <span class="math-container">$round(x)$</span>, the absolute rounding error <span class="math-container">$|round(x) - x|$</span> is going to be less than <code>0.5 ulp(E(x))</code>, where the <code>ulp</code> are units in the last place</p> <p><span class="math-container">$ulp(E) = 2^E \cdot \epsilon$</span></p> <p>and <span class="math-container">$E(x)$</span> is the exponent used for <span class="math-container">$x$</span>, and <span class="math-container">$\epsilon$</span> is the machine epsilon <span class="math-container">$\epsilon=2^{-(p-1)}$</span>, <span class="math-container">$p$</span> is precision (24 for the single precision and 53 for the double precision IEEE formats). </p> <p>Using this, the relative error can be expressed for any real number <span class="math-container">$x$</span></p> <p><span class="math-container">$e_r = |\frac{(round(x) - x)}{x}| = \frac{|(round(x) - x)|}{|x|} &lt; |0.5 \cdot 2^E \cdot 2^{-(p-1)}| / |2^E| &lt; 0.5 \epsilon$</span></p> <p>For denormalized numbers <span class="math-container">$0 &lt; x &lt; 2^Em \epsilon$</span>, where <code>Em</code> is the minimal exponent (-126 for single precision, -1022 for double):</p> <p><span class="math-container">$0 &lt; x \le 0.5 \cdot \epsilon \cdot 2^{Em}$</span></p> <p>the rounding always goes to <span class="math-container">$0$</span>! </p> <p>If the <code>round(x)</code> is 0, then by (1)</p> <p><span class="math-container">$e_r =|\frac{(0 - 1)}{1}| = |1|$</span> !</p> <p>How is the relative error computed for such numbers? Should the relative error be even used for the numbers that are rounded to <code>0</code>?</p> https://cs.stackexchange.com/q/100332 0 algorithm for correctly rounded floating point radix conversion Andreas H. https://cs.stackexchange.com/users/96642 2018-11-20T11:48:27Z 2019-08-18T02:01:15Z <p>Is there any generic algorithm which implements a floating point radix conversion? </p> <p>Lets say we have a <span class="math-container">$p$</span>-digit FP number</p> <p><span class="math-container">$A = \sum_{i=0}^{p-1} A_i \beta^{e-i}$</span></p> <p>in radix <span class="math-container">$\beta$</span> and with <span class="math-container">$0 \leq A_i &lt; \beta$</span>. </p> <p>How do we find the <span class="math-container">$A'_i$</span>, <span class="math-container">$e'$</span> values for the <span class="math-container">$p'$</span>-digit base <span class="math-container">$\gamma$</span> FP number</p> <p><span class="math-container">$A' = \sum_{i=0}^{p'-1} A'_i \gamma^{e'-i}$</span></p> <p>closest to <span class="math-container">$A$</span>?</p> <p>There is one <a href="https://cs.stackexchange.com/questions/80952/convert-a-decimal-floating-point-number-into-a-binary-floating-point-number">question</a> which explicitly asks about radix 2 to radix 10 conversion, but unfortunately the answers seem to be specific for these radix combination. Here I ask about the general case.</p> <p>Also is an intermediate arbitrary precision FP calculation really necessary? (as in the function <code>strtod</code> in David Gay's <a href="http://www.netlib.org/fp/dtoa.c" rel="nofollow noreferrer">dtoa.c</a>)</p> https://cs.stackexchange.com/q/112336 0 Floating point substraction devss https://cs.stackexchange.com/users/107639 2019-07-31T12:06:00Z 2019-07-31T12:06:00Z <p>if <span class="math-container">$x=1.0e38=1.0 * 10^{38}$</span> and <span class="math-container">$y=3.0$</span> <br> i want to find <span class="math-container">$(x-x)+y$</span> and <span class="math-container">$(x+y)-x$</span> <br> i think the value of (x-x)+y will be just substract <span class="math-container">$x-x=0 + y=3.0 = 3.0$</span> <br> but how can i perfom addition of different base? <span class="math-container">$(x+y)-x$</span> <br> i think the idea is addition <span class="math-container">$(x+y)$</span> then substract <span class="math-container">$-x$</span> using floating point, i tried to convert <span class="math-container">$y=3.0$</span> to binary such as <span class="math-container">$1.1 * 2^1$</span> <br> but how about <span class="math-container">$10^{38}$</span> to binary ?</p> https://cs.stackexchange.com/q/109831 0 Convert $1.75\times10^{15}$ to IEEE-32 format? Inside https://cs.stackexchange.com/users/105788 2019-05-25T08:54:17Z 2019-07-25T23:02:30Z <p><span class="math-container">$1.75\times10^{15}$</span></p> <p>I know how to convert decimal to binary </p> <p><span class="math-container">$(1.75)_{10}$</span> is equal to <span class="math-container">$(1.11)_2$</span></p> <p>But to represent <span class="math-container">$10^{15}$</span> is the main problem for me. I can solve the question but this is the point where I got stuck. How can I represent <span class="math-container">$10^{15}$</span> in base 2 ? </p> https://cs.stackexchange.com/q/112119 2 Polynomials - using Newton's method, or not? Bojan Vukasovic https://cs.stackexchange.com/users/107863 2019-07-23T18:20:03Z 2019-07-25T21:59:50Z <p>I have to find a root of polynomial of degree <span class="math-container">$n\ge2$</span>. I need to write code to calculate the root for different values of <span class="math-container">$n$</span>. Only 1 real positive solution is needed. </p> <p>I can use general Newton's method for all degrees, or only for 5th+, and for 2,3 and 4 I can use algebraic formulas that solve quadratic, cubic and quartic equations. Since algebraic formulas need to use sqrt, acos and similar functions - does it make sense at all to use algebraic formulas - or is it better to use Newton's method for all degrees? I guess the latter will actually be faster?</p> <p>This is my equation:</p> <p><span class="math-container">$$\frac{1}{(b_1x + 1)} + \frac{1}{(b_2x + 1)} + ... + \frac{1}{(b_nx + 1)} -k = 0$$</span></p> <p>and constraints:</p> <p><span class="math-container">$$1 \leq k&lt;n \\ b_n&gt;0$$</span></p> <p>e.g. for <span class="math-container">$n=3$</span>:</p> <p><span class="math-container">$$b_1 b_2 b_3 (-k)x^3 +\left(b_1 b_2+b_3 b_2+b_1 b_3- b_1 b_2 k-b_3 b_2 k-b_1 b_3 k\right)x^2 + \left(2 b_1+2 b_2+2 b_3-b_1 k-b_2 k-b_3 k\right)x + 3-k =0$$</span></p> <p>which can be written as</p> <p><span class="math-container">$$\sum_{i=0}^n(n-i-k)\binom{\{b_1,...,b_n\}}{i}x^i=0.$$</span> </p> https://cs.stackexchange.com/q/111944 1 How many floating point ops were performed worldwide over a time interval [closed] Trekkie https://cs.stackexchange.com/users/107679 2019-07-18T00:45:07Z 2019-07-18T00:45:07Z <p>I am looking for information regarding the evolution of computing capability. Specifically I would like to know how many floating point operations were performed worldwide from, say, the deployment of ENIAC to the first moon landing... Or any other time interval before, say, the '80s. is this a question that I can estimate based on existing data?</p> https://cs.stackexchange.com/q/111735 0 Computing an Expression Bob https://cs.stackexchange.com/users/47896 2019-07-11T21:20:40Z 2019-07-11T22:44:23Z <p>I am writing code to evaluate the following expression: <span class="math-container">$$\frac{(a+b+c)!}{a! b! c!}$$</span> where <span class="math-container">$a$</span>, <span class="math-container">$b$</span> and <span class="math-container">$c$</span> are on the range of <span class="math-container">$10$</span> to <span class="math-container">$500$</span>. The result is going to be a floating point number. I could use a big number package, but the code will run slowly. I am using 64-bit floating point numbers.</p> <p>I claim by doing as much of the computation in integer (maybe 64 bit) I will minimize the floating point round off error. Therefore, I claim that if put the integers to be multiplied together in an array, cancel common denominators, and then do the final computation in floating point I will minimize round off error.</p> <p>Do I have this right?</p> https://cs.stackexchange.com/q/110931 3 How much can we trust mathematical software when working with large numbers, and how much memory it needs to work with these numbers? Pinteco https://cs.stackexchange.com/users/92704 2019-06-19T20:45:22Z 2019-07-11T22:02:57Z <p>For example, I want to evaluate the expression:</p> <p><span class="math-container">$3^{3^{{3}^{3}}}$</span> </p> <p>so I used wolframalpha.com (it's free, and I don't own any software), which returned the scientific notation of the number above, namely:</p> <p><span class="math-container">$1.258014290627491317860390698... × 10^{3638334640024}$</span></p> <p>Which is <em>huge</em>. However, for the number below</p> <p><span class="math-container">$4^{4^{{4}^{4}}}$</span> </p> <p>Wolfram can't return a scientific notation, probably because it's a <em>much larger</em> number and it needs a lot of memory.</p> <blockquote> <p>Questions: a) How much can we trust that </p> </blockquote> <p><span class="math-container">$3^{3^{{3}^{3}}} \approx 1.258014290627491317860390698... × 10^{3638334640024}$</span> </p> <blockquote> <p>b) how much memory (aproximate) it needs to evaluate</p> </blockquote> <p><span class="math-container">$3^{3^{{3}^{3}}}$</span></p> <p>and </p> <p><span class="math-container">$4^{4^{{4}^{4}}}$</span></p> <p>I'm guessing a lot of terabytes and something that a home computer can't handle. But for the first number, Wolfram can, and the second number, it can't. How do we even find how much size we need to calculate these numbers?</p> https://cs.stackexchange.com/q/82246 1 Shortest decimal expansion within binary interval equaeghe https://cs.stackexchange.com/users/70565 2017-10-09T20:22:40Z 2019-07-08T12:05:19Z <p>Consider an interval <span class="math-container">$[x-2^n,x+2^n]$</span> defined by a binary float <span class="math-container">$x$</span> and a power of two <span class="math-container">$2^n$</span> typically much smaller than <span class="math-container">$x$</span>. I would like to know whether an efficient algorithm exists to determine the shortest decimal expansion within the interval. What is the basic idea of such an algorithm? Perhaps such an algorithm has already been published?</p> <p>In my own search, I have come across the work of <a href="https://doi.org/10.1145/93548.93559" rel="nofollow noreferrer">Steele &amp; White “How to print floating-point numbers accurately”</a>, but it is not clear to me whether it applies in the sense that their results can be adapted to this particular case.</p> https://cs.stackexchange.com/q/110798 2 numerically stable log1pexp calculation Yashas https://cs.stackexchange.com/users/66162 2019-06-17T11:55:57Z 2019-06-30T17:49:39Z <p>What are good approximations for computing <code>log1pexp</code> for single precision and double precision floating point numbers?</p> <p><strong>Note:</strong> <code>log1pexp(x)</code> is <code>log(1 + exp(x))</code></p> <p>I have found few implementations of <code>log1pexp</code> for double precision but they don't provide an explanation on how they arrived at the approximations. Hence, I am not able to implement <code>log1exp</code> for single precision numbers (without converting to double precision intermediates of course).</p> <p>Reference implementation: <a href="https://github.com/davisking/dlib/blob/master/dlib/dnn/utilities.h#L16-L29" rel="nofollow noreferrer">https://github.com/davisking/dlib/blob/master/dlib/dnn/utilities.h#L16-L29</a></p> https://cs.stackexchange.com/q/109939 2 Floating point arithmetic Maths2468 https://cs.stackexchange.com/users/59180 2019-05-27T17:43:35Z 2019-05-28T07:10:29Z <p>I need to change x1 = 0.3 and x2 = -0.29 to a FP(floating point) number with one sign bit, a 4 bit mantissa, a 3 bit exponent. The results I got are:</p> <p>x1: 0 001 0011</p> <p>x2: 1 001 0010</p> <p>I am also trying to calculate the number of significant digits of x1 and x2 and I have found 2 for each, but I am unsure of this result.</p> <p>The question also requires me to find z = (FP)x1 + (FP)x2 and the number of significant digits of z. But I am not sure how to proceed with this part of the question. Therefore, any guidance on how I could proceed would be greatly appreciated.</p> <p>Thank you very much!</p> https://cs.stackexchange.com/q/109235 3 Guarantees on computing $a+x(b-a)$ in floating point Doris https://cs.stackexchange.com/users/105169 2019-05-11T16:14:18Z 2019-05-19T23:17:28Z <p>I want to implement the function <span class="math-container">$f(x,a,b) = a + x(b-a)$</span> where all the inputs are floating point (doubles, say), such that (a) <span class="math-container">$f(0,a,b)=a$</span> exactly; (b) <span class="math-container">$f(1,a,b)=b$</span> exactly; (c) <span class="math-container">$f(x,a,b) \le f(y,a,b)$</span> whenever <span class="math-container">$x \le y$</span>; and preferably (d) it is accurate (correct up to rounding) for <span class="math-container">$0 \le x \le 1$</span>.</p> <p>Implementing <span class="math-container">$f(x,a,b)=a+x(b-a)$</span> directly does not work because for example <span class="math-container">$f(1.0,-1.0,\operatorname{prev}(1.0)) = 1.0$</span> (where <span class="math-container">$\operatorname{prev}(a)$</span> is the floating point number before <span class="math-container">$a$</span>). And <span class="math-container">$f(x,a,b)=b-(1-x)(b-a)$</span> has the same issue.</p> <p>Now <span class="math-container">$$f(x,a,b) = (1-x)(a+x(b-a))+x(b-(1-x)(b-a))$$</span> has the first two properties.</p> <ul> <li>Does it have property (c)?</li> <li>How accurate is it?</li> <li>Is there a more performant way to do this?</li> </ul> https://cs.stackexchange.com/q/106697 0 Float number to binary Mycroft https://cs.stackexchange.com/users/102687 2019-04-09T06:41:45Z 2019-05-09T21:21:20Z <p>I would like to convert 0,347 and 0,9828 to binary, how can I do that?</p> <p>I know that sucessive multiplication by 2 can do this, but this method seems very painful and even ineffective since the size of count.</p> <p>This is for a question, and I think that sucessive multiplication is needed. But, in 0,347, I did more than 20 multiplication and did not reach result. Is this normal?</p> https://cs.stackexchange.com/q/108856 0 How does normalised floating point binary work with two's complement? S. Dauncey https://cs.stackexchange.com/users/104769 2019-05-02T08:31:36Z 2019-05-02T11:50:08Z <p>I'm doing AQA a-level computer science, and the specification for which states that: </p> <p><em>Exam questions on floating point numbers will use a format in which both the normalised mantissa and exponent are represented using two's complement</em></p> <p>(despite this not being the IEEE standard). I can't find much information online about how a system would work with a mantissa that is both normalised and in two's complement. This is because I would guess that the mantissa has to represent a value between -1 and 1; however if we do this, then the same numbers can be expressed in multiple ways so I would not consider it normalised, for example:</p> <pre><code>1.0110 * 2^(3) = (-1 + 1/4 + 1/8) * 2^(3) = -5 </code></pre> <p>and</p> <pre><code>1.1011 * 2^(4) = (-1 + 1/2 + 1/8 + 1/16) * 2^(4) = -5 </code></pre> <p>From the <a href="https://www.aqa.org.uk/subjects/computer-science-and-it/as-and-a-level/computer-science-7516-7517/assessment-resources" rel="nofollow noreferrer">A-level Paper 2 June 2017</a> question 11, it seems that</p> <pre><code>1 . 0 0 0 0 0 0 0 | 0 0 1 0 </code></pre> <p>is considered a <em>negative normalised value</em> but</p> <pre><code>1 . 1 0 0 1 1 1 0 | 1 0 0 0 </code></pre> <p>isn't. Any enlightenment would be much appreciated.</p> <p>EDIT:</p> <p>The comment below explains the answer. For the value to count as "normalised", the absolute value of the mantissa must be between 1/2 and 1 which prevents double counting. This corresponds to the first two digits of the mantissa being 1.0 or 0.1 (so you could save on bits if you were actually implementing this).</p> https://cs.stackexchange.com/q/51576 0 What is the 1's and 2's complement of 0.01101? aste123 https://cs.stackexchange.com/users/15608 2016-01-07T11:42:16Z 2019-04-25T08:42:05Z <p>What is the 1's and 2's complement of 0.01101? I'm unable to find any details on this from google.</p> <p>Basically how do we represent the floating points in 1's and 2's complement forms?</p> <p>Even wikipedia only says that 1's complement is the inverted bits of binary representation. The examples only contain integer values. I couldn't find anything clear about what is the exact significance of this system. Hence, unable to deduce if the inverting bits applies to floating points also. </p> https://cs.stackexchange.com/q/107296 1 Where can I find some free benchmarks to evaluate a MCU? [closed] HYF https://cs.stackexchange.com/users/103229 2019-04-21T04:14:49Z 2019-04-21T04:14:49Z <p>At present, I'm designing a soft processor with single-precision floating point unit (FPU). I am going to put my soft core into an FPGA and do some performance evaluation. The benchmarks are supposed to contain many single-precision floating point calculations, such as fadd, fmul, fdiv and fsqrt. Therefore, I can know the speed-up provided by FPU. Besides, I also want to compare my soft core with popular cores from ARM such as Cortex-M0, M1, M3. Since ARM provides <code>DesignStart</code> of these cores, it should be easy to put them into an FPGA and do comparision.</p> <p>I only know 2 free benchmarks that could run on a soft core: Dhrystone and CoreMark. Can anyone share other free benchmarks for evaluation? Spending 1000+ dollars to buy a benchmark is not affordable for me.</p> https://cs.stackexchange.com/q/105757 0 Why isn't it necessary to store an integer part of significant in IEEE754 floating point notation? user366312 https://cs.stackexchange.com/users/101748 2019-03-18T22:03:54Z 2019-04-18T09:02:10Z <p>We see that there is a sign, exponent, and mantissa part for the notation. But, there is no location for the significant bit.</p> <p>Why isn't it necessary to store an integer part of significant in IEEE754 floating point notation?</p> https://cs.stackexchange.com/q/106402 2 Stable and fast computation of the squared euclidean distance matrix Celelibi https://cs.stackexchange.com/users/22833 2019-04-03T05:27:42Z 2019-04-06T02:13:20Z <p>Let's say I want to compute the matrix <span class="math-container">$M$</span> of the squared euclidean distances between each pair of vectors <span class="math-container">$(x, y)$</span> belonging to two sets <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> respectively. The sets of vectors <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> have size <span class="math-container">$m$</span> and <span class="math-container">$n$</span>. Each vector has <span class="math-container">$k$</span> floating point coordinates.</p> <p>As far as I can tell, there are mainly two ways to implement the computation of an euclidean distance matrix. The <em>direct formula</em>, which is slow but accurate, and the <em>expanded formula</em> which can be fast but numerically inaccurate. I'm wondering if there would be a way to compute the squared euclidean distance matrix in a stable and fast way.</p> <p>The direct formula compute for each pair of vector <span class="math-container">$x \in X$</span> and <span class="math-container">$y \in Y$</span>: <span class="math-container">$\sum_i (x_i - y_i)^2$</span>. It is pretty accurate and could even be combined a with <a href="https://en.wikipedia.org/wiki/Kahan_summation_algorithm" rel="nofollow noreferrer">compensated summation</a> algorithm. It is however relatively slow as this is an <span class="math-container">$\mathcal{O}(mnk)$</span> algorithm and can only take advantage of level 1 BLAS routines.</p> <p>On the other hand, the expanded formula compute <span class="math-container">$\sum_i{x_i^2} + \sum_i{y_i^2} - 2\sum_i{x_i y_i}$</span>. It is pretty fast as it only makes 2/3 of the operations of the direct formula and can use the BLAS matrix multiplication for the last term. Unfortunately, it is numerically very unstable and often produce negative result.</p> <p>Intuitively, the computation of an euclidean distance matrix seems very redundant when <span class="math-container">$k \ll min(m, n)$</span>. Once we know the distance from a vector <span class="math-container">$x \in X$</span> to <span class="math-container">$k+1$</span> vectors from <span class="math-container">$Y$</span>, then the distance from <span class="math-container">$x$</span> to all the other vectors <span class="math-container">$y \in Y$</span> are pretty much determined. But I can't find a useful way to exploit this redundancy to make less computations.</p> <p>Side note: the expanded formula also gives us an upper bound on the minimal reachable complexity of the computation of the euclidean matrix. Since its complexity is basically that of the matrix multiplication, it is theoretically possible to compute the euclidean distance matrix in <span class="math-container">$\mathcal{O}(n^{2.3737})$</span>. But maybe there's a structure to the squared euclidean distance matrix that would make this bound practical. Who knows?</p> https://cs.stackexchange.com/q/106314 4 Proof that (x-y)(x+y) is more accurate than x²-y² Celelibi https://cs.stackexchange.com/users/22833 2019-04-01T00:10:07Z 2019-04-02T23:10:54Z <p>I was <a href="https://cs.stackexchange.com/q/106152/22833">carrying on</a> my reading of <a href="https://www.itu.dk/~sestoft/bachelor/IEEE754_article.pdf" rel="nofollow noreferrer">What Every Computer Scientist Should Know About Floating-Point Arithmetic</a> but got stuck on the proof of Theorem 2 (page 34).</p> <p>At some point it says: <span class="math-container">\begin{align} (x \otimes x) \ominus (y \otimes y) &amp; = \left[x^2(1 + \delta_1) - y^2(1 + \delta_2)\right](1 + \delta_3) \\ &amp; = \left[(x^2 - y^2)(1 + \delta_1) + (\delta_1 - \delta_2)y^2\right](1 + \delta_3) \\ \end{align}</span> I'm ok with the rewriting, but I don't understand the argument that:</p> <blockquote> <p>When <span class="math-container">$x$</span> and <span class="math-container">$y$</span> are nearby, the error term <span class="math-container">$(\delta_1 - \delta_2)y^2$</span> can be as large as the result <span class="math-container">$x^2 - y^2$</span>.</p> </blockquote> <p>This doesn't make much sens to me right now. I understand that if both quantities are close to each other, then the relative error is close to <span class="math-container">$1$</span>. But not why they should be close to each other.</p> https://cs.stackexchange.com/q/106152 2 Proof that a guard digit bound the error of subtraction Celelibi https://cs.stackexchange.com/users/22833 2019-03-28T00:01:16Z 2019-03-29T00:01:24Z <p>I was reading <a href="https://www.itu.dk/~sestoft/bachelor/IEEE754_article.pdf" rel="nofollow noreferrer">What Every Computer Scientist Should Know About Floating-Point Arithmetic</a>, which is extremely interesting. But I have some troubles understanding the proof of Theorem 9 (page 33).</p> <p>First a pretty trivial question. When the formula <span class="math-container">$(15)$</span> say: <span class="math-container">$$y - \bar{y} \lt (\beta - 1)(\beta^{-p} + \dots + \beta^{-p-k})$$</span> Shouldn't it be <span class="math-container">$\le$</span> instead of <span class="math-container">$\lt$</span>, or did I miss something?</p> <p>More importantly, I do not understand why it say that <em>if <span class="math-container">$x-\bar{y} \lt 1$</span>, then <span class="math-container">$\delta = 0$</span></em>. How can there be no rounding error?</p> <p>It is then said that: <span class="math-container">$$x - y \ge 1.0 - 0.\overbrace{0 \dots 0}^k\overbrace{\rho \dots \rho}^k \; \textrm{with} \; \rho = \beta - 1$$</span></p> <p>Why is that so? Can't the difference be arbitrarily small or even <span class="math-container">$0$</span>? Why would there be as many <span class="math-container">$\rho$</span>'s as there are <span class="math-container">$0$</span>'s?</p> https://cs.stackexchange.com/q/105565 -2 Doubt in definition of Float Random user https://cs.stackexchange.com/users/101564 2019-03-14T04:27:08Z 2019-03-14T13:59:06Z <p>Can anyone tell the meaning of the bold portion?</p> <blockquote> <p>Float: It is used to store decimal numbers <strong>(numbers with floating point value) with single precision.</strong></p> </blockquote> https://cs.stackexchange.com/q/102542 0 IEEE754 representation in hexadecimal? Luke https://cs.stackexchange.com/users/77791 2019-01-07T18:42:05Z 2019-03-11T02:20:58Z <p>In class, I've heard hexadecimal representation for IEEE754 mentioned and described in 32bit length as a format that consists of one bit for sign, normalized 6-digit fraction (with an implied leading zero) and biased (+64) 7bit exponent, leading me to believe it's not just a made up spec. </p> <p>However, googling the actual IEEE754-2008 standard, I've found only 5 basic formats for base 2 and base 10 in it (binary32, binary64, binary128, decimal64, decimal128) and some more interchange formats for these two bases, but no mention of representation in base 16. Could that specification be some rejected proposal which is difficult to find now or am I missing something here?</p>