Timeline for Multiplying intervals in Two's complement
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 13, 2013 at 13:34 | comment | added | Yuval Filmus | @Odin GMP implements multiplication of large numbers "in two's complement" efficiently. It's open source so you can check out the code. Or better, you can just use this library. | |
| Jun 13, 2013 at 9:06 | comment | added | Odin | @YuvalFilmus Why do you think it's impossible? The sum interval can also be out of range, but it it indeed possible to implement the interval-addition efficient and 100% correct. Also there is obviously a trivial solution to the problem (just use brute force), but i want the same thing efficient (logarithmic or constant time) | |
| Jun 6, 2013 at 14:53 | history | edited | John K. | CC BY-SA 3.0 |
added math, formatted
|
| Jun 6, 2013 at 7:30 | review | Close votes | |||
| Jun 6, 2013 at 14:53 | |||||
| Jun 6, 2013 at 7:13 | comment | added | Yuval Filmus | @Odin It is impossible since the correct product interval is out of range. | |
| Jun 5, 2013 at 9:05 | comment | added | Odin | @YuvalFilmus and why is it impossible then? There's no need to calculate the endpoints of the resulting interval this way. | |
| May 30, 2013 at 16:58 | history | tweeted | twitter.com/#!/StackCompSci/status/340150238146863104 | ||
| May 30, 2013 at 14:32 | comment | added | Yuval Filmus | @Odin It is actually impossible. The endpoints of the resulting interval are formed by multiplying appropriate endpoints of the original intervals. | |
| May 30, 2013 at 11:17 | comment | added | Odin | @YuvalFilmus It is possible, that the for $[a, b]*[c, d]$, $b*d$ overflows $n$ times and $a*c$ overflows $n-1$ times, then, there is possibly a value $e \in [a, b]$ and $f \in [c, d]$ for which $e*f > b*d$ and $e*f > a*c$. This makes the problem highly non-trivial | |
| May 29, 2013 at 23:24 | comment | added | Yuval Filmus | In that case, what is the relevance of interval arithmetic? It seems that the question is only about multiplication of integers. | |
| May 29, 2013 at 17:49 | comment | added | Odin | @YuvalFilmus Because of the overflows it seems very hard to compute for example $[2146731546, 2146731854]*[-2144714992, -2144714893] = [-1474518098, 1600169696]$ | |
| May 29, 2013 at 17:40 | history | edited | Odin | CC BY-SA 3.0 |
deleted 3 characters in body
|
| May 29, 2013 at 17:10 | comment | added | Yuval Filmus | What is the relevance of the numbers being represented using two's complement? | |
| May 29, 2013 at 17:10 | answer | added | Yuval Filmus | timeline score: 1 | |
| May 29, 2013 at 16:52 | comment | added | torquestomp | $7+(-6)=1$, not $-1$ | |
| May 29, 2013 at 16:41 | history | edited | Odin | CC BY-SA 3.0 |
added 51 characters in body
|
| May 29, 2013 at 16:36 | comment | added | Odin | @YuvalFilmus I added a definition and an example, does that help? | |
| May 29, 2013 at 16:22 | history | edited | Odin | CC BY-SA 3.0 |
added 829 characters in body
|
| May 29, 2013 at 15:57 | comment | added | Yuval Filmus | What are interval operations? | |
| May 29, 2013 at 15:43 | history | asked | Odin | CC BY-SA 3.0 |