1// Copyright 2010 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package big
6
7import (
8	"math"
9	"testing"
10)
11
12func TestZeroRat(t *testing.T) {
13	var x, y, z Rat
14	y.SetFrac64(0, 42)
15
16	if x.Cmp(&y) != 0 {
17		t.Errorf("x and y should be both equal and zero")
18	}
19
20	if s := x.String(); s != "0/1" {
21		t.Errorf("got x = %s, want 0/1", s)
22	}
23
24	if s := x.RatString(); s != "0" {
25		t.Errorf("got x = %s, want 0", s)
26	}
27
28	z.Add(&x, &y)
29	if s := z.RatString(); s != "0" {
30		t.Errorf("got x+y = %s, want 0", s)
31	}
32
33	z.Sub(&x, &y)
34	if s := z.RatString(); s != "0" {
35		t.Errorf("got x-y = %s, want 0", s)
36	}
37
38	z.Mul(&x, &y)
39	if s := z.RatString(); s != "0" {
40		t.Errorf("got x*y = %s, want 0", s)
41	}
42
43	// check for division by zero
44	defer func() {
45		if s := recover(); s == nil || s.(string) != "division by zero" {
46			panic(s)
47		}
48	}()
49	z.Quo(&x, &y)
50}
51
52func TestRatSign(t *testing.T) {
53	zero := NewRat(0, 1)
54	for _, a := range setStringTests {
55		x, ok := new(Rat).SetString(a.in)
56		if !ok {
57			continue
58		}
59		s := x.Sign()
60		e := x.Cmp(zero)
61		if s != e {
62			t.Errorf("got %d; want %d for z = %v", s, e, &x)
63		}
64	}
65}
66
67var ratCmpTests = []struct {
68	rat1, rat2 string
69	out        int
70}{
71	{"0", "0/1", 0},
72	{"1/1", "1", 0},
73	{"-1", "-2/2", 0},
74	{"1", "0", 1},
75	{"0/1", "1/1", -1},
76	{"-5/1434770811533343057144", "-5/1434770811533343057145", -1},
77	{"49832350382626108453/8964749413", "49832350382626108454/8964749413", -1},
78	{"-37414950961700930/7204075375675961", "37414950961700930/7204075375675961", -1},
79	{"37414950961700930/7204075375675961", "74829901923401860/14408150751351922", 0},
80}
81
82func TestRatCmp(t *testing.T) {
83	for i, test := range ratCmpTests {
84		x, _ := new(Rat).SetString(test.rat1)
85		y, _ := new(Rat).SetString(test.rat2)
86
87		out := x.Cmp(y)
88		if out != test.out {
89			t.Errorf("#%d got out = %v; want %v", i, out, test.out)
90		}
91	}
92}
93
94func TestIsInt(t *testing.T) {
95	one := NewInt(1)
96	for _, a := range setStringTests {
97		x, ok := new(Rat).SetString(a.in)
98		if !ok {
99			continue
100		}
101		i := x.IsInt()
102		e := x.Denom().Cmp(one) == 0
103		if i != e {
104			t.Errorf("got IsInt(%v) == %v; want %v", x, i, e)
105		}
106	}
107}
108
109func TestRatAbs(t *testing.T) {
110	zero := new(Rat)
111	for _, a := range setStringTests {
112		x, ok := new(Rat).SetString(a.in)
113		if !ok {
114			continue
115		}
116		e := new(Rat).Set(x)
117		if e.Cmp(zero) < 0 {
118			e.Sub(zero, e)
119		}
120		z := new(Rat).Abs(x)
121		if z.Cmp(e) != 0 {
122			t.Errorf("got Abs(%v) = %v; want %v", x, z, e)
123		}
124	}
125}
126
127func TestRatNeg(t *testing.T) {
128	zero := new(Rat)
129	for _, a := range setStringTests {
130		x, ok := new(Rat).SetString(a.in)
131		if !ok {
132			continue
133		}
134		e := new(Rat).Sub(zero, x)
135		z := new(Rat).Neg(x)
136		if z.Cmp(e) != 0 {
137			t.Errorf("got Neg(%v) = %v; want %v", x, z, e)
138		}
139	}
140}
141
142func TestRatInv(t *testing.T) {
143	zero := new(Rat)
144	for _, a := range setStringTests {
145		x, ok := new(Rat).SetString(a.in)
146		if !ok {
147			continue
148		}
149		if x.Cmp(zero) == 0 {
150			continue // avoid division by zero
151		}
152		e := new(Rat).SetFrac(x.Denom(), x.Num())
153		z := new(Rat).Inv(x)
154		if z.Cmp(e) != 0 {
155			t.Errorf("got Inv(%v) = %v; want %v", x, z, e)
156		}
157	}
158}
159
160type ratBinFun func(z, x, y *Rat) *Rat
161type ratBinArg struct {
162	x, y, z string
163}
164
165func testRatBin(t *testing.T, i int, name string, f ratBinFun, a ratBinArg) {
166	x, _ := new(Rat).SetString(a.x)
167	y, _ := new(Rat).SetString(a.y)
168	z, _ := new(Rat).SetString(a.z)
169	out := f(new(Rat), x, y)
170
171	if out.Cmp(z) != 0 {
172		t.Errorf("%s #%d got %s want %s", name, i, out, z)
173	}
174}
175
176var ratBinTests = []struct {
177	x, y      string
178	sum, prod string
179}{
180	{"0", "0", "0", "0"},
181	{"0", "1", "1", "0"},
182	{"-1", "0", "-1", "0"},
183	{"-1", "1", "0", "-1"},
184	{"1", "1", "2", "1"},
185	{"1/2", "1/2", "1", "1/4"},
186	{"1/4", "1/3", "7/12", "1/12"},
187	{"2/5", "-14/3", "-64/15", "-28/15"},
188	{"4707/49292519774798173060", "-3367/70976135186689855734", "84058377121001851123459/1749296273614329067191168098769082663020", "-1760941/388732505247628681598037355282018369560"},
189	{"-61204110018146728334/3", "-31052192278051565633/2", "-215564796870448153567/6", "950260896245257153059642991192710872711/3"},
190	{"-854857841473707320655/4237645934602118692642972629634714039", "-18/31750379913563777419", "-27/133467566250814981", "15387441146526731771790/134546868362786310073779084329032722548987800600710485341"},
191	{"618575745270541348005638912139/19198433543745179392300736", "-19948846211000086/637313996471", "27674141753240653/30123979153216", "-6169936206128396568797607742807090270137721977/6117715203873571641674006593837351328"},
192	{"-3/26206484091896184128", "5/2848423294177090248", "15310893822118706237/9330894968229805033368778458685147968", "-5/24882386581946146755650075889827061248"},
193	{"26946729/330400702820", "41563965/225583428284", "1238218672302860271/4658307703098666660055", "224002580204097/14906584649915733312176"},
194	{"-8259900599013409474/7", "-84829337473700364773/56707961321161574960", "-468402123685491748914621885145127724451/396955729248131024720", "350340947706464153265156004876107029701/198477864624065512360"},
195	{"575775209696864/1320203974639986246357", "29/712593081308", "410331716733912717985762465/940768218243776489278275419794956", "808/45524274987585732633"},
196	{"1786597389946320496771/2066653520653241", "6269770/1992362624741777", "3559549865190272133656109052308126637/4117523232840525481453983149257", "8967230/3296219033"},
197	{"-36459180403360509753/32150500941194292113930", "9381566963714/9633539", "301622077145533298008420642898530153/309723104686531919656937098270", "-3784609207827/3426986245"},
198}
199
200func TestRatBin(t *testing.T) {
201	for i, test := range ratBinTests {
202		arg := ratBinArg{test.x, test.y, test.sum}
203		testRatBin(t, i, "Add", (*Rat).Add, arg)
204
205		arg = ratBinArg{test.y, test.x, test.sum}
206		testRatBin(t, i, "Add symmetric", (*Rat).Add, arg)
207
208		arg = ratBinArg{test.sum, test.x, test.y}
209		testRatBin(t, i, "Sub", (*Rat).Sub, arg)
210
211		arg = ratBinArg{test.sum, test.y, test.x}
212		testRatBin(t, i, "Sub symmetric", (*Rat).Sub, arg)
213
214		arg = ratBinArg{test.x, test.y, test.prod}
215		testRatBin(t, i, "Mul", (*Rat).Mul, arg)
216
217		arg = ratBinArg{test.y, test.x, test.prod}
218		testRatBin(t, i, "Mul symmetric", (*Rat).Mul, arg)
219
220		if test.x != "0" {
221			arg = ratBinArg{test.prod, test.x, test.y}
222			testRatBin(t, i, "Quo", (*Rat).Quo, arg)
223		}
224
225		if test.y != "0" {
226			arg = ratBinArg{test.prod, test.y, test.x}
227			testRatBin(t, i, "Quo symmetric", (*Rat).Quo, arg)
228		}
229	}
230}
231
232func TestIssue820(t *testing.T) {
233	x := NewRat(3, 1)
234	y := NewRat(2, 1)
235	z := y.Quo(x, y)
236	q := NewRat(3, 2)
237	if z.Cmp(q) != 0 {
238		t.Errorf("got %s want %s", z, q)
239	}
240
241	y = NewRat(3, 1)
242	x = NewRat(2, 1)
243	z = y.Quo(x, y)
244	q = NewRat(2, 3)
245	if z.Cmp(q) != 0 {
246		t.Errorf("got %s want %s", z, q)
247	}
248
249	x = NewRat(3, 1)
250	z = x.Quo(x, x)
251	q = NewRat(3, 3)
252	if z.Cmp(q) != 0 {
253		t.Errorf("got %s want %s", z, q)
254	}
255}
256
257var setFrac64Tests = []struct {
258	a, b int64
259	out  string
260}{
261	{0, 1, "0"},
262	{0, -1, "0"},
263	{1, 1, "1"},
264	{-1, 1, "-1"},
265	{1, -1, "-1"},
266	{-1, -1, "1"},
267	{-9223372036854775808, -9223372036854775808, "1"},
268}
269
270func TestRatSetFrac64Rat(t *testing.T) {
271	for i, test := range setFrac64Tests {
272		x := new(Rat).SetFrac64(test.a, test.b)
273		if x.RatString() != test.out {
274			t.Errorf("#%d got %s want %s", i, x.RatString(), test.out)
275		}
276	}
277}
278
279func TestIssue2379(t *testing.T) {
280	// 1) no aliasing
281	q := NewRat(3, 2)
282	x := new(Rat)
283	x.SetFrac(NewInt(3), NewInt(2))
284	if x.Cmp(q) != 0 {
285		t.Errorf("1) got %s want %s", x, q)
286	}
287
288	// 2) aliasing of numerator
289	x = NewRat(2, 3)
290	x.SetFrac(NewInt(3), x.Num())
291	if x.Cmp(q) != 0 {
292		t.Errorf("2) got %s want %s", x, q)
293	}
294
295	// 3) aliasing of denominator
296	x = NewRat(2, 3)
297	x.SetFrac(x.Denom(), NewInt(2))
298	if x.Cmp(q) != 0 {
299		t.Errorf("3) got %s want %s", x, q)
300	}
301
302	// 4) aliasing of numerator and denominator
303	x = NewRat(2, 3)
304	x.SetFrac(x.Denom(), x.Num())
305	if x.Cmp(q) != 0 {
306		t.Errorf("4) got %s want %s", x, q)
307	}
308
309	// 5) numerator and denominator are the same
310	q = NewRat(1, 1)
311	x = new(Rat)
312	n := NewInt(7)
313	x.SetFrac(n, n)
314	if x.Cmp(q) != 0 {
315		t.Errorf("5) got %s want %s", x, q)
316	}
317}
318
319func TestIssue3521(t *testing.T) {
320	a := new(Int)
321	b := new(Int)
322	a.SetString("64375784358435883458348587", 0)
323	b.SetString("4789759874531", 0)
324
325	// 0) a raw zero value has 1 as denominator
326	zero := new(Rat)
327	one := NewInt(1)
328	if zero.Denom().Cmp(one) != 0 {
329		t.Errorf("0) got %s want %s", zero.Denom(), one)
330	}
331
332	// 1a) a zero value remains zero independent of denominator
333	x := new(Rat)
334	x.Denom().Set(new(Int).Neg(b))
335	if x.Cmp(zero) != 0 {
336		t.Errorf("1a) got %s want %s", x, zero)
337	}
338
339	// 1b) a zero value may have a denominator != 0 and != 1
340	x.Num().Set(a)
341	qab := new(Rat).SetFrac(a, b)
342	if x.Cmp(qab) != 0 {
343		t.Errorf("1b) got %s want %s", x, qab)
344	}
345
346	// 2a) an integral value becomes a fraction depending on denominator
347	x.SetFrac64(10, 2)
348	x.Denom().SetInt64(3)
349	q53 := NewRat(5, 3)
350	if x.Cmp(q53) != 0 {
351		t.Errorf("2a) got %s want %s", x, q53)
352	}
353
354	// 2b) an integral value becomes a fraction depending on denominator
355	x = NewRat(10, 2)
356	x.Denom().SetInt64(3)
357	if x.Cmp(q53) != 0 {
358		t.Errorf("2b) got %s want %s", x, q53)
359	}
360
361	// 3) changing the numerator/denominator of a Rat changes the Rat
362	x.SetFrac(a, b)
363	a = x.Num()
364	b = x.Denom()
365	a.SetInt64(5)
366	b.SetInt64(3)
367	if x.Cmp(q53) != 0 {
368		t.Errorf("3) got %s want %s", x, q53)
369	}
370}
371
372func TestFloat32Distribution(t *testing.T) {
373	// Generate a distribution of (sign, mantissa, exp) values
374	// broader than the float32 range, and check Rat.Float32()
375	// always picks the closest float32 approximation.
376	var add = []int64{
377		0,
378		1,
379		3,
380		5,
381		7,
382		9,
383		11,
384	}
385	var winc, einc = uint64(5), 15 // quick test (~60ms on x86-64)
386	if *long {
387		winc, einc = uint64(1), 1 // soak test (~1.5s on x86-64)
388	}
389
390	for _, sign := range "+-" {
391		for _, a := range add {
392			for wid := uint64(0); wid < 30; wid += winc {
393				b := 1<<wid + a
394				if sign == '-' {
395					b = -b
396				}
397				for exp := -150; exp < 150; exp += einc {
398					num, den := NewInt(b), NewInt(1)
399					if exp > 0 {
400						num.Lsh(num, uint(exp))
401					} else {
402						den.Lsh(den, uint(-exp))
403					}
404					r := new(Rat).SetFrac(num, den)
405					f, _ := r.Float32()
406
407					if !checkIsBestApprox32(t, f, r) {
408						// Append context information.
409						t.Errorf("(input was mantissa %#x, exp %d; f = %g (%b); f ~ %g; r = %v)",
410							b, exp, f, f, math.Ldexp(float64(b), exp), r)
411					}
412
413					checkNonLossyRoundtrip32(t, f)
414				}
415			}
416		}
417	}
418}
419
420func TestFloat64Distribution(t *testing.T) {
421	// Generate a distribution of (sign, mantissa, exp) values
422	// broader than the float64 range, and check Rat.Float64()
423	// always picks the closest float64 approximation.
424	var add = []int64{
425		0,
426		1,
427		3,
428		5,
429		7,
430		9,
431		11,
432	}
433	var winc, einc = uint64(10), 500 // quick test (~12ms on x86-64)
434	if *long {
435		winc, einc = uint64(1), 1 // soak test (~75s on x86-64)
436	}
437
438	for _, sign := range "+-" {
439		for _, a := range add {
440			for wid := uint64(0); wid < 60; wid += winc {
441				b := 1<<wid + a
442				if sign == '-' {
443					b = -b
444				}
445				for exp := -1100; exp < 1100; exp += einc {
446					num, den := NewInt(b), NewInt(1)
447					if exp > 0 {
448						num.Lsh(num, uint(exp))
449					} else {
450						den.Lsh(den, uint(-exp))
451					}
452					r := new(Rat).SetFrac(num, den)
453					f, _ := r.Float64()
454
455					if !checkIsBestApprox64(t, f, r) {
456						// Append context information.
457						t.Errorf("(input was mantissa %#x, exp %d; f = %g (%b); f ~ %g; r = %v)",
458							b, exp, f, f, math.Ldexp(float64(b), exp), r)
459					}
460
461					checkNonLossyRoundtrip64(t, f)
462				}
463			}
464		}
465	}
466}
467
468// TestSetFloat64NonFinite checks that SetFloat64 of a non-finite value
469// returns nil.
470func TestSetFloat64NonFinite(t *testing.T) {
471	for _, f := range []float64{math.NaN(), math.Inf(+1), math.Inf(-1)} {
472		var r Rat
473		if r2 := r.SetFloat64(f); r2 != nil {
474			t.Errorf("SetFloat64(%g) was %v, want nil", f, r2)
475		}
476	}
477}
478
479// checkNonLossyRoundtrip32 checks that a float->Rat->float roundtrip is
480// non-lossy for finite f.
481func checkNonLossyRoundtrip32(t *testing.T, f float32) {
482	if !isFinite(float64(f)) {
483		return
484	}
485	r := new(Rat).SetFloat64(float64(f))
486	if r == nil {
487		t.Errorf("Rat.SetFloat64(float64(%g) (%b)) == nil", f, f)
488		return
489	}
490	f2, exact := r.Float32()
491	if f != f2 || !exact {
492		t.Errorf("Rat.SetFloat64(float64(%g)).Float32() = %g (%b), %v, want %g (%b), %v; delta = %b",
493			f, f2, f2, exact, f, f, true, f2-f)
494	}
495}
496
497// checkNonLossyRoundtrip64 checks that a float->Rat->float roundtrip is
498// non-lossy for finite f.
499func checkNonLossyRoundtrip64(t *testing.T, f float64) {
500	if !isFinite(f) {
501		return
502	}
503	r := new(Rat).SetFloat64(f)
504	if r == nil {
505		t.Errorf("Rat.SetFloat64(%g (%b)) == nil", f, f)
506		return
507	}
508	f2, exact := r.Float64()
509	if f != f2 || !exact {
510		t.Errorf("Rat.SetFloat64(%g).Float64() = %g (%b), %v, want %g (%b), %v; delta = %b",
511			f, f2, f2, exact, f, f, true, f2-f)
512	}
513}
514
515// delta returns the absolute difference between r and f.
516func delta(r *Rat, f float64) *Rat {
517	d := new(Rat).Sub(r, new(Rat).SetFloat64(f))
518	return d.Abs(d)
519}
520
521// checkIsBestApprox32 checks that f is the best possible float32
522// approximation of r.
523// Returns true on success.
524func checkIsBestApprox32(t *testing.T, f float32, r *Rat) bool {
525	if math.Abs(float64(f)) >= math.MaxFloat32 {
526		// Cannot check +Inf, -Inf, nor the float next to them (MaxFloat32).
527		// But we have tests for these special cases.
528		return true
529	}
530
531	// r must be strictly between f0 and f1, the floats bracketing f.
532	f0 := math.Nextafter32(f, float32(math.Inf(-1)))
533	f1 := math.Nextafter32(f, float32(math.Inf(+1)))
534
535	// For f to be correct, r must be closer to f than to f0 or f1.
536	df := delta(r, float64(f))
537	df0 := delta(r, float64(f0))
538	df1 := delta(r, float64(f1))
539	if df.Cmp(df0) > 0 {
540		t.Errorf("Rat(%v).Float32() = %g (%b), but previous float32 %g (%b) is closer", r, f, f, f0, f0)
541		return false
542	}
543	if df.Cmp(df1) > 0 {
544		t.Errorf("Rat(%v).Float32() = %g (%b), but next float32 %g (%b) is closer", r, f, f, f1, f1)
545		return false
546	}
547	if df.Cmp(df0) == 0 && !isEven32(f) {
548		t.Errorf("Rat(%v).Float32() = %g (%b); halfway should have rounded to %g (%b) instead", r, f, f, f0, f0)
549		return false
550	}
551	if df.Cmp(df1) == 0 && !isEven32(f) {
552		t.Errorf("Rat(%v).Float32() = %g (%b); halfway should have rounded to %g (%b) instead", r, f, f, f1, f1)
553		return false
554	}
555	return true
556}
557
558// checkIsBestApprox64 checks that f is the best possible float64
559// approximation of r.
560// Returns true on success.
561func checkIsBestApprox64(t *testing.T, f float64, r *Rat) bool {
562	if math.Abs(f) >= math.MaxFloat64 {
563		// Cannot check +Inf, -Inf, nor the float next to them (MaxFloat64).
564		// But we have tests for these special cases.
565		return true
566	}
567
568	// r must be strictly between f0 and f1, the floats bracketing f.
569	f0 := math.Nextafter(f, math.Inf(-1))
570	f1 := math.Nextafter(f, math.Inf(+1))
571
572	// For f to be correct, r must be closer to f than to f0 or f1.
573	df := delta(r, f)
574	df0 := delta(r, f0)
575	df1 := delta(r, f1)
576	if df.Cmp(df0) > 0 {
577		t.Errorf("Rat(%v).Float64() = %g (%b), but previous float64 %g (%b) is closer", r, f, f, f0, f0)
578		return false
579	}
580	if df.Cmp(df1) > 0 {
581		t.Errorf("Rat(%v).Float64() = %g (%b), but next float64 %g (%b) is closer", r, f, f, f1, f1)
582		return false
583	}
584	if df.Cmp(df0) == 0 && !isEven64(f) {
585		t.Errorf("Rat(%v).Float64() = %g (%b); halfway should have rounded to %g (%b) instead", r, f, f, f0, f0)
586		return false
587	}
588	if df.Cmp(df1) == 0 && !isEven64(f) {
589		t.Errorf("Rat(%v).Float64() = %g (%b); halfway should have rounded to %g (%b) instead", r, f, f, f1, f1)
590		return false
591	}
592	return true
593}
594
595func isEven32(f float32) bool { return math.Float32bits(f)&1 == 0 }
596func isEven64(f float64) bool { return math.Float64bits(f)&1 == 0 }
597
598func TestIsFinite(t *testing.T) {
599	finites := []float64{
600		1.0 / 3,
601		4891559871276714924261e+222,
602		math.MaxFloat64,
603		math.SmallestNonzeroFloat64,
604		-math.MaxFloat64,
605		-math.SmallestNonzeroFloat64,
606	}
607	for _, f := range finites {
608		if !isFinite(f) {
609			t.Errorf("!IsFinite(%g (%b))", f, f)
610		}
611	}
612	nonfinites := []float64{
613		math.NaN(),
614		math.Inf(-1),
615		math.Inf(+1),
616	}
617	for _, f := range nonfinites {
618		if isFinite(f) {
619			t.Errorf("IsFinite(%g, (%b))", f, f)
620		}
621	}
622}
623