Algorithm 6.1 (GenDot) works as follows. The condition number (5.7) of the dot product xT y is proportional to the degree of cancellation. In order to achieve a prescribed cancellation, we generate the first half of the vectors x and y randomly within a large exp
(n, c)
| 1503 | return [lo + width * i for i in range(n)] |
| 1504 | |
| 1505 | def GenDot(n, c): |
| 1506 | """ Algorithm 6.1 (GenDot) works as follows. The condition number (5.7) of |
| 1507 | the dot product xT y is proportional to the degree of cancellation. In |
| 1508 | order to achieve a prescribed cancellation, we generate the first half of |
| 1509 | the vectors x and y randomly within a large exponent range. This range is |
| 1510 | chosen according to the anticipated condition number. The second half of x |
| 1511 | and y is then constructed choosing xi randomly with decreasing exponent, |
| 1512 | and calculating yi such that some cancellation occurs. Finally, we permute |
| 1513 | the vectors x, y randomly and calculate the achieved condition number. |
| 1514 | """ |
| 1515 | |
| 1516 | assert n >= 6 |
| 1517 | n2 = n // 2 |
| 1518 | x = [0.0] * n |
| 1519 | y = [0.0] * n |
| 1520 | b = log2(c) |
| 1521 | |
| 1522 | # First half with exponents from 0 to |_b/2_| and random ints in between |
| 1523 | e = choices(range(int(b/2)), k=n2) |
| 1524 | e[0] = int(b / 2) + 1 |
| 1525 | e[-1] = 0.0 |
| 1526 | |
| 1527 | x[:n2] = [uniform(-1.0, 1.0) * exp2(p) for p in e] |
| 1528 | y[:n2] = [uniform(-1.0, 1.0) * exp2(p) for p in e] |
| 1529 | |
| 1530 | # Second half |
| 1531 | e = list(map(round, linspace(b/2, 0.0 , n-n2))) |
| 1532 | for i in range(n2, n): |
| 1533 | x[i] = uniform(-1.0, 1.0) * exp2(e[i - n2]) |
| 1534 | y[i] = (uniform(-1.0, 1.0) * exp2(e[i - n2]) - DotExact(x, y)) / x[i] |
| 1535 | |
| 1536 | # Shuffle |
| 1537 | pairs = list(zip(x, y)) |
| 1538 | shuffle(pairs) |
| 1539 | x, y = zip(*pairs) |
| 1540 | |
| 1541 | return DotExample(x, y, DotExact(x, y), Condition(x, y)) |
| 1542 | |
| 1543 | def RelativeError(res, ex): |
| 1544 | x, y, target_sumprod, condition = ex |