[ mona / prog / sol ]

prog


Challenge^2: Floating Point without Errors

1 2020-10-16 10:11

https://rosettacode.org/wiki/Pathological_floating_point_problems
Implement this RC challenge, without loading external libraries/programs in your favorite language(standard library parts are allowed).

Rules:
1. All three tasks must be solved exactly - no errors.
2. No loading any external programs or libraries.
3. Solution should be as laconic as possible: you are allowed to implement anything but larger solutions will be treated as weaker than shorter ones.

2 2020-10-16 12:03

https://rosettacode.org/wiki/Pathological_floating_point_problems#PicoLisp

3 2020-10-16 13:31

I didn't realize that Chez Scheme lacked arbitrary precision reals. The following can compute the rational values fairly easily for Task 1. What Scheme implementations do have arbitrary precision reals, just out of curiosity.

(def-memo (v n)
    (case n
      ((1) 2)
      ((2) -4)
      (else
       (+ 111 (/ -1130 (v (- n 1))) (/ 3000 (* (v (- n 1)) (v (- n 2))))))))
4 2020-10-16 13:36

>>3
Ah, I'm using my memoize macro as well, you can see that: http://0x0.st/iDz7.scm

5 2020-10-16 17:37

Task 3 is also easy:

(define (task-3 a b)
  (+ (* (+ 333 3/4) (expt b 6))
     (* (expt a 2) (- (* 11 (expt a 2) (expt b 2))
                      (expt b 6)
                      (* 121 (expt b 4))
                      2))
     (* (+ 5 1/2) (expt b 8))
     (/ a (* 2 b))))

(display "Task 3:\n")
(let ((result (task-3 77617 33096)))
  (display `(,result (approx: ,(exact->inexact result)))))
(newline)

>>3
Irrational numbers have an infinite number of non-repeating decimals, the only exact way to represent them is symbolic:

(define (task-2 years)
  (let loop ((n 1) (e 1) (m 1))
    (if (<= n years)
        (loop (+ n 1) (* e n) (+ (* m n) 1))
        `(- (* ,e e) ,m))))

(display "Task 2:\n")
(display (task-2 25))
(newline)
6 2020-10-16 17:51

>>5

Irrational numbers have an infinite number of non-repeating decimals, the only exact way to represent them is symbolic

Yes of course, by definition, but some implementations have real numbers which are only limited by the size of memory, right? Not to get too off topic but the fact that real numbers can only be represented as a process which produces them given infinite computational power really does give a lot of merit to the finitist position. Either that or a rejection of mathematical objects as the fundamental building block of mathematics rather than processes.

7 2020-10-16 19:15
import decimal
import math
import sys

if sys.version_info[:3] < (3,):
   print('https://www.python.org/doc/sunset-python-2/')
   exit(-1)

decimal.getcontext().prec = 150
d = decimal.Decimal

print('task 1')

v = {'n-2' : d(2), 'n-1' : d(-4.0)}

for n in range(3, 101):
   v['n'] = 111 - 1130 / v['n-1'] + 3000 / (v['n-1'] * v['n-2'])
   v['n-2'], v['n-1'] = v['n-1'], v['n']
   if n in [3,4,5,6,7,8,20,30,50,100]:
      print('v[%d] = %.16f' % (n, v['n']))

print('task 2')

balance = d('2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642742746') - 1

for year in range(1,26):
   balance = balance * year - 1

print('Balance after %d years: %.16f' % (year, balance))

print('task 3')

a = d(77617.0)
b = d(33096.0)

def f(a,b):
   return d(333.75) * b**6 + a**2 * (11 * a**2 * b**2 - b**6 - 121 * b**4 - 2) + d(5.5) * b**8 + a / (2 * b)

print('f(%.1f, %.1f) = %.15f' % (a, b, f(a, b)))
8 2020-10-17 00:38 *

>>7

Should be:

if sys.version_info[:3] < (3,):
    eval('print "https://www.python.org/doc/sunset-python-2/"')
    exit(-1)

Remember when print was a keyword?

9 2020-10-17 08:17

>>8

print("something")

should also work with python 2, the parentheses are evaluated away.

10 2020-10-18 02:00

>>6
Mathemathics has(excluding non-standard analysis) belief infinite series have a final number as result, not its limit:
0.999...=1(9/10+9/10^2+...=1.0 implying 1-1/10^n=1)

11 2020-10-18 02:12

>>10 Btw there is "pathological example" for 0.999...!=1
1. assume 1=0.999... , transform right parts to series
2. 1=9/10+9/10^2+9/10^n+.... ,substracting equals results in 0
3. 1-9/10-9/10^2-9/10^n-...=0 ,transform into series of divisions
4.10/10 -9/10 -> 10/100 -> -9/100-> 1/10 -> 1/10/10/10/10/10...=0
5. 1/10/10/...=1/10^n=0 , now multiply both sides by 10^n
6 1=0*10^n=0 , i.e. 1=0

12 2020-10-18 02:28

>>11
Doesn't this disprove >>10 by contradiction? I guess it's like the liar paradox where despite the contradiction effectively refuting the research program mathematicians choose to ignore it. Also does every irrational number have a series which converges to it, probably?

13 2020-10-18 03:51

>>12
Mathemathicians define there is a limit, which a series(representing a number, as a process) converges to,
They make the philosophical leap of equating the 'limit' with a concrete number that has not been computed or fully represented(due being infinite). This error largely stems from the infinite series formula discarding the 'limit to 0' part of finite series formula;
This is only series formula that is indisputable(infinite formula is a castrated version of it):
Note "the proof" relies on this( 1−rn+1 and rn+1 → 0 for | r | < 1. ):
https://en.wikipedia.org/wiki/Geometric_series#Proof_of_convergence

14 2020-10-18 05:56

Floating point: insignificant differences add up to large differences.
Mathematicians defining limits: *sweat nervously* "So um (*Autistic screeching*) well, the limit is just the sum of series, basically(*inhales*): Its the result. The Science is Settled."

The modern definition of a limit (for any ε there exists an index N so that ...) was given by Bernhard Bolzano (Der binomische Lehrsatz, Prague 1816, little noticed at the time), and by Karl Weierstrass in the 1870s.
https://en.wikipedia.org/wiki/Limit_of_a_sequence#History

15 2020-10-18 06:07

I find it ironic people can intuitively understand why material object speed can only approach c, but be never equal to it.
Imagine an object that is traveling at 0.9c accelerating to 0.99c(+0.09c)
1.each hour the object accelerates by 10% of previous acceleration.
e.g. 0.9c,0.99c,0.999c,0.9999c
2.Will its speed will be equal to c at any time?

16 2020-10-18 06:55

>>14 Speaking of autistic screeching, this is how they justify the modern concept of a 'limit' equal to result.
https://en.wikipedia.org/wiki/(%CE%B5,_%CE%B4)-definition_of_limit#Informal_statement
https://en.wikipedia.org/wiki/Archimedean_property
These two are just arbitrary axioms that are convenient for modern theory, without correctly representing reality(same thing with "quanta of energy" see https://archive.org/details/arxiv-1005.1058 ) but

17 2020-10-18 07:07

People often comment that Math is divorced from reality, but they can't explain how. Its the continuum
https://en.wikipedia.org/wiki/Continuum_(measurement)
Reality isn't a VR sim with pixels(or 'quanta' in physics terms).
Math is modeled on theory which excludes infinitesimals, introducing the idea of 'minimal object' above zero(the Quanta of Math is the first real number above) of which all numbers have a finite quantity thereof(since its the smallest element to which numbers can be decomposed into, because infinitesimals can't exist in Modern Math) like pixels; this is of course the reductio ad absurdum of archimedean property.
This "Virtual Reality Math" only works until its foundations are investigated logically..but people follow what is convinient

18 2020-10-18 07:41

The "Pathological Error of specific floating-point unit design";
This is how this will solved in hardware:
https://www.computer.org/csdl/pds/api/csdl/proceedings/download-article/12OmNBcAGLd/pdf

19 2020-10-18 09:08

>>10-12
Hopefully this will make clear the fault in the reasoning:
http://mathb.in/46191?key=1c502c8c80fe309fb9ffd50d02664a8f654d82da

20 2020-10-18 09:18

>>19
Find n which satisfies 0!=0*10^n then

21 2020-10-18 09:28

>>20

22 2020-10-18 09:42

>>21 Time to introduce some infinite cardinals.
The expression 0*(10^n) is equivalent to
0*(10*10*10*...) what it means to multiply by 10? 10*x=x+x+x+(10 times)
so the form of this series can converted to 0*(10+10+10+10+...)
what is value of n*(x+y+z)? (x*n)+(n*y)+(n*z);
the values of expression becomes ((10*0)+(10*0)+(10*0)+...)
simplified to 0+0+0+0... ,where each step of the series is compacted 0+0=0 to zero, giving exactly 0 at every step, resulting in 0.

23 2020-10-18 09:50 *

>>22
Infinity is not a number, you can't treat it as such.

24 2020-10-18 10:03

>>23
At which point the series 0+0+0+... results in non-zero result? At every step(0+0) the result is zero.

25 2020-10-18 10:08

>>25
Try calculating it for an infinite number of terms by hand, I'll wait until you finish.

26 2020-10-18 10:16

>>25
0+0+0+... is a series where each step adds 0(except initial)
0(+0)(+0)(+0)... combine with the property of zero, is that it doesn't alter the result of number, when its added x+0=x
With this we can conclude that each op(+0) doesn't alter the result of number before it. https://en.wikipedia.org/wiki/Additive_identity

Since the series consists of NOPs which don't alter results of previous computation and don't add extra computation with more steps, the only significant number is the initial 0.

27 2020-10-18 11:52 *

For those who might wonder where the error >>11 is but do not wish to engage, the "5. 1/10/10/...=1/10^n=0" is properly "5. 1/10/10/...=lim[n->inf]1/10^n=0", which is just 0=0 and the lim[n->inf] bit is not subject to handwaving. There is no real number you can multiply "lim[n->inf]1/10^n" with to get 1.

28 2020-10-18 12:37

>>27
Its not required to represent the series as 1/10^n(its merely for convenience ):
1/10/10/10/10/... can be converted to a series of multiplications
1*(1/10)*(1/10)*(1/10)*...=0
Now we move the series to the right by dividing the 0 by
1=0/(1/10)/(1/10)/(1/10)/... division by 1/10 is equivalent to multiplying by 10/1, which result in
1=0*10*10*10*10... which was already already discussed here >>22
And shown to be equal exactly 0.

29 2020-10-18 13:16

>>18
I love this, thank you for sharing!

>>14-17
I didn't expect to see anyone more passionate about this topic than I. You can prove the Archimedean Property, and you don't have to prove definitions, though.

>>20-26
This is very silly. (I actually thought is 0*n=0 was part of the ordered-field axioms; it's not, but it's easily proven from them)

>>27
That makes sense.

30 2020-10-18 13:26

You can prove the Archimedean Property

Post any proof.

31 2020-10-18 13:35

>>30

The set N of natural numbers is unbounded above in R.

If N were bounded above, then by the completeness axiom it would have a least upper bound, say sup N = m. Since m is a least upper bound, m – 1 is not an upper bound of N. Thus there exists an n in N such that n > m – 1. But then n + 1 > m , and since n + 1 ∈ N, this contradicts m being an upper bound of N . ♦

(from "Analysis with Introduction to Proof" 5th edition)

32 2020-10-18 13:38

>>31

The set N of natural numbers is unbounded above in R.

And how this prevents existence of infinitesimals?

33 2020-10-18 13:47

>>32
That proof can also be used to prove that for every number r ∈ R, there exists an n ∈ N, such that 0 < 1/n < r.

34 2020-10-18 13:58

>>33
Wouldn't this just proof infinitesimals(1/N (1/10^n)) existing?

35 2020-10-18 14:10

>>34
tbh, it seems like it depends how you define R, and N. In either case it seems like if you have infinitesimals, and infinities they have to be comparable, and if R has infinitesimals, or infinities N has to have infinities. This does not necessitate the existence of infinitesimals though.

36 2020-10-18 14:22

Maybe there is another proof of Archimedean property you like to share?

37 2020-10-18 14:34

>>36
I think I'm fine with that proof. It's a very useful property used in many proofs, but it doesn't seem to be what the Wikipedia article linked earlier in the thread claims. The Wikipedia article bases its claim beyond those I gave on the idea that infinities and infinitesimals are incomparable, which I'm fairly certain all non-standard analysis reject. The textbook I used never claimed that infinitesimals and infinities were impossible due to the Archemidean property.

38 2020-10-18 14:45

>>37
The problem here is modern definition of real numbers relies on Archimedean property as axiom. i.e. trying to prove Archimedean property relying on 'real numbers' is circular Archimedean property relying on Archimedean property.

39 2020-10-18 14:50

>>38

The problem here is modern definition of real numbers relies on Archimedean property as axiom.

That's not true actually, the real numbers in standard analysis are uniquely defined as the (Dedekind-)complete ordered field.

40 2020-10-18 14:51

>>39
``For example, in the context of ordered fields, one has the axiom of Archimedes which formulates this property, where the field of real numbers is Archimedean``
https://en.wikipedia.org/wiki/Archimedean_property

41 2020-10-18 14:58

>>40
I haven't studied abstract algebra yet, but the ordered field definition I'm aware of does not rely on the Archimedean property as an axiom, and as was shown in >>30 this is provable as a theorem and does not need to be an axiom (this is not from the same book but I'm fairly certain these are the same properties):

http://math.colorado.edu/~packer/Orderedfieldaxioms300120.pdf

42 2020-10-18 15:01

>>41
Ordered field of real numbers is a specific subset of ordered field, which does rely on it.

43 2020-10-18 15:07

>>42
So the argument is that the completeness axiom is equivalent to the Archimedean property in the set of ordered fields? Since the completeness axiom uniquely applies to the real numbers in the set of ordered fields this would mean that the Archimedean property would uniquely apply to the real numbers in the set of ordered fields. So a counter-example can disprove this claim, namely the rational numbers.

44 2020-10-18 15:22

>>43
Wikipedia has a weaselly definition of it:
``When the real numbers are instead constructed using a model, completeness becomes a theorem or collection of theorems.``
https://en.wikipedia.org/wiki/Completeness_of_the_real_numbers#Forms_of_completeness

45 2020-10-18 15:26

On the least upper bound property
Axiom 4, which requires the order to be Dedekind-complete, implies the Archimedean property.
https://en.wikipedia.org/wiki/Construction_of_the_real_numbers#On_the_least_upper_bound_property

46 2020-10-18 15:28

'Real numbers' status: Debunked as irrational drivel.

47 2020-10-18 15:29

>>43
I'm not familiar with this, what does it mean to construct the reals using a model. Also out of curiosity does non-standard analysis define the reals in a different way? I'd be curious to see their definitions.

48 2020-10-18 15:33

>>47
https://mathworld.wolfram.com/NonstandardAnalysis.html
The wikipedia article is likely some sort of trolling.

49 2020-10-18 15:34

>>45
This was already proven in >>31 the question was if Dedkind-complete ordered field was equivalent to the Archimedean ordered field. That is Dedkind-complete ordered field iff Archimedian ordered field. Which was already dis-proven by the existence of a non-Dedkind-complete ordered field which was Archimedian, namely the rational numbers.

50 2020-10-18 15:36

The wikipedia article in question(90% disinfo or misleading):
https://en.wikipedia.org/wiki/Nonstandard_analysis

51 2020-10-18 15:48

>>50 *they moved the juicy criticism section here:
https://en.wikipedia.org/wiki/Criticism_of_nonstandard_analysis

52 2020-10-18 16:00 *

>>50
That is wikipaedo.

53 2020-10-18 16:16

>>50
Its amazing how people can twist facts and invent problems on the spot when they feel the topic is against their worldview.
This article suppose to be 100% neutral boring math, yet at every line it attacks Non-standard analysis, denies existence of infinitesimal calculus as its direct predecessor or invents problems specific to current definitions that exclude infinitesimals apriori.

54 2020-10-18 16:27

>>53
Also it gives impression that its based on pedagogical problems with
"current definition of a limit" and hints of relation to intuitionism
while Robinson proved non-standard analysis with rigor.
the narrative and selective quotes, give
the overall impression of flimsy,irrational system that can't compete with
standard analysis - something more suited to academic studies on 'social impact of math' and various philosophical works.

55 2020-10-18 16:44

I have not be as emotionally invested in "infinitesimals" "limit definition" and "Archimedean property" if these were not based on "Science is Settled" arguments that don't have logical basis.
(note: i don't deny that some areas of math are highly controversial like
ultrafinitism, which many view as Flat Earth is viewed by geologists)
The current mathematics structure is like a house of cards relying on
axioms that aren't acknowledged as axioms or proved by circular logic where proofs are relying on systems constructed using these axioms.
When a contradiction in a system is spotted, the usual reply that "its wrong due X"
ignores that X itself is a products of current system and alternatives to X don't exist or aren't developed(due lack of interest or paradigm dominance).

56 2020-10-18 16:57 *

>>48,50,51
I tried to watch a lecture on non-standard analysis, but they basically built this new large field R(x) composed of rational functions such that R ⊃ R(x). Such that R(x) does not satisfy the Archimedian Property, and is not Dedikind-Complete, but then threw it out because it wasn't sufficient for some reason. I'm a bit tired now, but I might watch the second part of the lecture series where they actually define R*. I couldn't find any definitions online which I could understand with my current mathematical abilities.

57 2020-10-18 17:14 *

I meant R ⊂ R(x), sorry.

58 2020-10-20 09:54 *

For those who might wonder where the error >>28 is but do not wish to engage, the step from "1*(1/10)*(1/10)*(1/10)*...=0" to "1=0/(1/10)/(1/10)/(1/10)/..." repeats the same fallacy >>27 because "1*(1/10)*(1/10)*(1/10)*..." is lim[n->inf](1/10)^n and there is no real number that you can multiply it with to ever get 1 back.

As for the archimedean trolling, you can dismiss it entirely. The proof is quite simple. If a field is ordered and is non-archimedean then it is incomplete, but R is both ordered and complete, thus R is archimedean. The other proof that was posted >>31 >>33 is also valid.

59


VIP:

do not edit these