Arithmetic/Rational: Difference between revisions

 

Define a new type called '''frac''' with binary operator "//" of two integers that returns a '''structure''' made up of the numerator and the denominator (as per a rational number).

 

Use the new type '''frac''' to find all [[Perfect Numbers|perfect numbers]] less than 2¹⁹ by summing the reciprocal of the factors.

 

 

=={{header|Ada}}==

{{works with|ALGOL 68|Standard - no extensions to language used}}

{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}

FORMAT frac repr = $g(-0)"//"g(-0)$;

candidate, ENTIER sum, real sum, ENTIER sum = 1))

FI

{{out}}

<pre>

Sum of reciprocal factors of 523776 = 2 exactly, about 2.0000000000000000000000000005

</pre>

 

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

DIM frac{num, den}

DIM Sum{} = frac{}, Kf{} = frac{}, One{} = frac{}

a.num /= a : a.den /= a

IF a.den < 0 a.num *= -1 : a.den *= -1

Output:

<pre>

=={{header|C}}==

C does not have overloadable operators. The following implementation <u>''does not define all operations''</u> so as to keep the example short. Note that the code passes around struct values instead of pointers to keep it simple, a practice normally avoided for efficiency reasons.

#include <stdlib.h>

#define FMT "%lld"

 

return 0;

See [[Rational Arithmetic/C]]

 

<div style="text-align:right;font-size:7pt">''<nowiki>[</nowiki>This section is included from [[Arithmetic/Rational/C sharp|a subpage]] and should be edited there, not here.<nowiki>]</nowiki>''</div>

{{:Arithmetic/Rational/C sharp}}

{{libheader|Boost}}

Boost provides a rational number template.

#include "math.h"

#include "boost/rational.hpp"

}

return 0;

 

=={{header|Clojure}}==

Ratios are built in to Clojure and support math operations already. They automatically reduce and become Integers if possible.

22/7

user> 34/2

17

user> (+ 37/5 42/9)

 

=={{header|Common Lisp}}==

Common Lisp has rational numbers built-in and integrated with all other number types. Common Lisp's number system is not extensible so reimplementing rational arithmetic would require all-new operator names.

for sum = (+ (/ candidate)

(loop for factor from 2 to (isqrt candidate)

sum (+ (/ factor) (/ (floor candidate factor)))))

when (= sum 1)

 

=={{header|D}}==

 

// std.numeric.gcd doesn't work with BigInt.

}

}

Use the <code>-version=rational_arithmetic_main</code> compiler switch to run the test code.

{{out}}

Sum of recipr. factors of 523776 = 2 exactly.</pre>

Currently RationalT!BigInt is not fast.

 

=={{header|Elisa}}==

type Rational;

Rational(Numerator = integer, Denominater = integer) -> Rational;

else GCD (A, mod(B,A)) ];

 

Tests

 

PerfectNumbers( Limit = integer) -> multi(integer);

];

 

{{out}}

<pre>

</pre>

 

 

=={{header|F_Sharp|F#}}==

The F# Powerpack library defines the BigRational data type.

 

let perf n = 1N = List.fold (+) 0N (List.map (fun i -> if n % i = 0 then 1N/frac.FromInt(i) else 0N) [2..n])

 

 

=={{header|Forth}}==

\ Uses the stack convention of the built-in "*/" for int * frac -> int

 

 

: rat-inc tuck + swap ;

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

 

implicit none

end function rational_modulo

 

Example:

 

use module_rational

end do

 

{{out}}

<pre>6

496

8128</pre>

 

=={{header|GAP}}==

Rational numbers are built-in.

# true

2/3 + 3/4;

 

=={{header|Go}}==

 

Code here implements the perfect number test described in the task using the standard library.

 

import (

}

}

{{out}}

<pre>

=={{header|Groovy}}==

Groovy does not provide any built-in facility for rational arithmetic. However, it does support arithmetic operator overloading. Thus it is not too hard to build a fairly robust, complete, and intuitive rational number class, such as the following:

final BigInteger num, denom

 

Rational(BigDecimal decimal) {

this(

}

 

 

private List reduce(BigInteger n, BigInteger d) {

(n, d) = [n.abs(), d.abs()]

BigInteger commonFactor = gcd(n, d)

}

 

 

private BigInteger gcd(BigInteger n, BigInteger m) {

Object asType(Class type) {

switch (type) {

default: throw new ClassCastException("Cannot convert from type Rational to type " + type)

}

 

int compareTo(o) {

: (Double.NaN as int)

}

"${num}//${denom}"

}

 

The following ''RationalCategory'' class allows for modification of regular ''Number'' behavior when interacting with ''Rational''.

 

class RationalCategory {

: DefaultGroovyMethods.asType(a, type)

}

 

Test Program (mixes the ''RationalCategory'' methods into the ''Number'' class):

 

def x = [5, 20] as Rational

catch (Throwable t) { println t.message }

try { println (α as char) }

{{out}}

<pre style="height:30ex;overflow:scroll;">1//4

</pre>

The following uses the ''Rational'' class, with ''RationalCategory'' mixed into ''Number'', to find all perfect numbers less than 2¹⁹:

 

def factorize = { target ->

def trackProgress = { if ((it % (100*1000)) == 0) { println it } else if ((it % 1000) == 0) { print "." } }

 

{{out}}

<pre>...................................................................................................100000

=={{header|Haskell}}==

Haskell provides a <code>Rational</code> type, which is really an alias for <code>Ratio Integer</code> (<code>Ratio</code> being a polymorphic type implementing rational numbers for any <code>Integral</code> type of numerators and denominators). The fraction is constructed using the <code>%</code> operator.

 

 

For a sample implementation of <code>Ratio</code>, see [http://www.haskell.org/onlinereport/ratio.html the Haskell 98 Report].

Additional procedures are implemented here to complete the task:

* 'makerat' (make), 'absrat' (abs), 'eqrat' (=), 'nerat' (~=), 'ltrat' (<), 'lerat' (<=), 'gerat' (>=), 'gtrat' (>)

limit := 2^19

 

if rsum.numer = rsum.denom = 1 then

return c

{{out}}

<pre>Perfect numbers up to 524288 (using rational arithmetic):

Testing absrat( (-1/1), ) ==> returned (1/1)</pre>

The following task functions are missing from the IPL:

return write("Testing ",p,"( ",rat2str(r1),", ",rat2str(\r2) | &null," ) ==> ","returned " || rat2str(p(r1,r2)) | "failed")

end

end

 

The {{libheader|Icon Programming Library}} provides [http://www.cs.arizona.edu/icon/library/src/procs/rational.icn rational] and [http://www.cs.arizona.edu/icon/library/src/procs/numbers.icn gcd in numbers]. Record definition and usage is shown below:

 

addrat(r1,r2) # Add rational numbers r1 and r2.

subrat(r1,r2) # Subtract rational numbers r1 and r2.

 

 

=={{header|J}}==

That said, note that J's floating point numbers work just fine for the stated problem:

Faster version (but the problem, as stated, is still tremendously inefficient):

Exhaustive testing would take forever:

6 28 496 8128

I.is_perfect_rational@x:@"0 i.2^19x

More limited testing takes reasonable amounts of time:

 

=={{header|Java}}==

Uses BigRational class: [[Arithmetic/Rational/Java]]

}

}

{{out}}

6 is a perfect number

28 is a perfect number

{{:Arithmetic/Rational/JavaScript}}

 

 

 

 

end

end

=={{header|Liberty BASIC}}==

Testing all numbers up to 2 ^ 19 takes an excessively long time.

n=2^19

for testNumber=1 to n

end if

end function

 

 

=={{header|Maple}}==

Maple has full built-in support for arithmetic with fractions (rational numbers). Fractions are treated like any other number in Maple.

> a := 3 / 5;

a := 3/5

> denom( a );

5

However, while you can enter a fraction such as "4/6", it will automatically be reduced so that the numerator and denominator have no common factor:

> b := 4 / 6;

b := 2/3

All the standard arithmetic operators work with rational numbers. It is not necessary to call any special routines.

> a + b;

19

> a - 1;

-2/5

Notice that fractions are treated as exact quantities; they are not converted to floats. However, you can get a floating point approximation to any desired accuracy by applying the function evalf to a fraction.

> evalf( 22 / 7 ); # default is 10 digits

3.142857143

3.142857142857142857142857142857142857142857142857142857142857142857\

142857142857142857142857142857143

 

Mathematica has full support for fractions built-in. If one divides two exact numbers it will be left as a fraction if it can't be simplified. Comparison, addition, division, product et cetera are built-in:

3/8

8/4

 

Numerator[6/9]

gives back:

<pre>1/4

3</pre>

As you can see, Mathematica automatically handles fraction as exact things, it doesn't evaluate the fractions to a float. It only does this when either the numerator or the denominator is not exact. I only showed integers above, but Mathematica can handle symbolic fraction in the same and complete way:

(b^2 - c^2)/(b - c) // Cancel

gives back:

b+c

Moreover it does simplification like Sin[x]/Cos[x] => Tan[x]. Division, addition, subtraction, powering and multiplication of a list (of any dimension) is automatically threaded over the elements:

gives back:

To check for perfect numbers in the range 1 to 2^25 we can use:

CheckPerfect[num_Integer]:=If[Total[1/Divisors[num]]==2,AppendTo[found,num]];

Do[CheckPerfect[i],{i,1,2^25}];

gives back:

Final note; approximations of fractions to any precision can be found using the function N.

 

=={{header|Maxima}}==

a: 3 / 11;

3/11

 

ratnump(a);

 

=={{header|Modula-2}}==

{{:Arithmetic/Rational/Modula-2}}

 

 

proc `^`[T](base, exp: T): T =

type Rational* = tuple[num, den: int64]

 

result.num = x

result.den = 1

if sum.den == 1:

echo "Sum of recipr. factors of ",candidate," = ",sum.num," exactly ",

Output:

<pre>Sum of recipr. factors of 6 = 1 exactly perfect!

 

=={{header|Objective-C}}==

 

=={{header|OCaml}}==

OCaml's Num library implements arbitrary-precision rational numbers:

open Num;;

 

Printf.printf "Sum of recipr. factors of %d = %d exactly %s\n%!"

candidate (int_of_num !sum) (if int_of_num !sum = 1 then "perfect!" else "")

[http://forge.ocamlcore.org/projects/pa-do/ Delimited overloading] can be used to make the arithmetic expressions more readable:

for candidate = 2 to 1 lsl 19 do

let sum = ref Num.(1 / of_int candidate) in

Printf.printf "Sum of recipr. factors of %d = %d exactly %s\n%!"

candidate Num.(to_int !sum) (if Num.(!sum = 1) then "perfect!" else "")

 

 

=={{header|ooRexx}}==

loop candidate = 6 to 2**19

sum = .fraction~new(1, candidate)

end

 

::method init

expose numerator denominator

use strict arg numerator, denominator = 1

 

 

-- if the denominator is negative, make the numerator carry the sign

 

::requires rxmath library

Output:

<pre>

=={{header|PARI/GP}}==

Pari handles rational arithmetic natively.

s=0;

fordiv(n,d,s+=1/d);

if(s==2,print(n))

 

=={{header|Perl}}==

Perl's <code>Math::BigRat</code> core module implements arbitrary-precision rational numbers. The <code>bigrat</code> pragma can be used to turn on transparent BigRat support:

 

foreach my $candidate (2 .. 2**19) {

print "Sum of recipr. factors of $candidate = $sum exactly ", ($sum == 1 ? "perfect!" : ""), "\n";

}

 

 

 

=={{header|PicoLisp}}==

 

(for (N 2 (> (** 2 19) N) (inc N))

"Perfect " N

", sum is " (car Sum)

{{out}}

<pre>Perfect 6, sum is 1: perfect

Perfect 523776, sum is 2</pre>

 

=={{header|Python}}==

{{works with|Python|3.0}}

Python 3's standard library already implements a Fraction class:

 

for candidate in range(2, 2**19):

if sum.denominator == 1:

print("Sum of recipr. factors of %d = %d exactly %s" %

It might be implemented like this:

return a // gcd(a,b) * b

 

return float(self.numerator / self.denominator)

def __int__(self):

 

=={{header|Racket}}==

 

Example:

-> (* 1/7 14)

2

 

=={{header|REXX}}==

end /*j*/

z_=z.2

end /*j*/

 

select

when op=='**' | op=='↑' |,

end /*select*/

 

if u==1 then return t

return t'/'u

'''output'''

<pre>

 

=={{header|Ruby}}==

for candidate in 2 .. 2**19

sum = Rational(1, candidate)

if candidate % factor == 0

sum += Rational(1, factor) + Rational(1, candidate / factor)

[candidate, sum.to_i, sum == 1 ? "perfect!" : ""]

end

{{out}}

<pre>

</pre>

 

 

 

=={{header|Scala}}==

{

require(d!=0)

def apply(n:Long)=new Rational(n)

implicit def longToRational(i:Long)=new Rational(i)

 

{

for (candidate <- 2 until 1<<19)

printf("Perfect number %d sum is %s\n", candidate, sum)

}

 

=={{header|Seed7}}==

in the library [http://seed7.sourceforge.net/libraries/bigrat.htm bigrat.s7i].

 

include "rational.s7i";

 

end if;

end for;

 

{{out}}

496 is perfect

8128 is perfect

</pre>

 

=={{header|Slate}}==

Slate uses infinite-precision fractions transparently.

20 reciprocal.

(5 / 6) reciprocal.

 

=={{header|Smalltalk}}==

<pre>st> 54/7

54/7

0.8333333333333334

</pre>

2 to: (2 raisedTo: 19) do: [ :candidate |

sum := candidate reciprocal.

ifFalse: [ ' ' ] }) displayNl

]

 

=={{header|Tcl}}==

{{incomplete|TI-89 BASIC}}

While TI-89 BASIC has built-in rational and symbolic arithmetic, it does not have user-defined data types.