The babylonian iterative method is the same as the Newton-Raphson method. Just that Newton's method is more generalized but when you use the particular equation i posted before you come to the babylonian formula so its basically the same thing.
The babylonian iterative method is the same as the Newton-Raphson method. Just that Newton's method is more generalized but when you use the particular equation i posted before you come to the babylonian formula so its basically the same thing.
http://verminox.wordpress.com - Answers to Life, the Universe and Everything
Here you go:
I could have also used gmp_prob_prime() to determ if the given number is a prime, but I felt its part of the challenge to create an own prime test.PHP Code:
#!/usr/bin/php
<?php
/**
* Programming Challenge 2006/12/29
* http://www.ubuntuforums.org/showthread.php?t=327334
*
* Task:
* 1. Reducing a fraction
* (a) Your input will be a floating number. You have to convert it into
* fraction form and reduce the fraction in the form
* Numerator/Denominator in its lowest reducable form.
*
* eg. Input: 0.3 ; Output: 3/10
* eg. Input 1.8 ; Output: 9/5
*
* (b) Same as above, but instead of a floating number you will given a
* numerator and denominator as input which is not in reduced form,
* you have to reduce it.
*
* eg. Input: 121 99 ; Output: 11/9
*
* The two are basically the same thing, but (a) requires converting a
* float to a fraction.... but in that case you always have a power of 10
* as the denominator so part (b) will take care of generalizing it for
* all pairs of numerator/denominator.
*
* 2. The Prime Test
* Since the above seemed simple, I decided to extend it a bit. Once you
* find the reduced fraction for either part (a) from a float or for
* part (b) from a given pair of Numerator and Denominator......
* you have to check if the sum of the numerator and denominator is a
* prime number or not.
*
* eg. If your fraction in reduced form is 3/10, the sum is 3+10 = 13
* which is prime, but if the fraction is 11/9, then 11+9=20 is not prime.
* You have to output the boolean result.
*/
// {{{ defines
/*
* input for task 1a. Must be float
*/
define('INPUT_1A', (float) 0.3);
/*
* input for task 1b. numerator and denominator
*/
define('INPUT_1B_NUM', (int) 121);
define('INPUT_1B_DEN', (int) 99);
// }}}
// {{{ functions
/**
* float2fraction()
*
* converts a floating point number to the lowest reducable fraction
*
* @input float $floatInput
* @return string fraction in the form "numerator/denominator"
*/
function float2fraction($floatInput)
{
$intDenominator = 1;
$floatNumerator = $floatInput;
while (ceil($floatNumerator) != $floatNumerator)
{
$intDenominator++;
$floatNumerator = $floatInput * $intDenominator;
}
$intNumerator = (int) $floatNumerator;
return $intNumerator ."/". $intDenominator;
}
/**
* reduceFraction()
*
* reduces numerator, denominator to the lowest reducable form
*
* @input int $intNumerator
* @input int $intDenominator
* @return string lowest reducable fraction in the form
* "numerator/denominator"
*/
function reduceFraction($intNumerator, $intDenominator)
{
$floatNumber = (float) $intNumerator / $intDenominator;
return float2fraction($floatNumber);
}
/**
* isPrime()
*
* checks if the given integer is a prime
*
* @input int $int
*
* @return bool
*/
function isPrime($int)
{
/*
* integer lower than two cannot be a prime
*/
if ($int < 2)
{
return false;
}
/*
* two is a prime and a special case
*/
if ($int == 2)
{
return true;
}
/*
* each prime greater than two has to be odd
*/
if (($int % 2) == 0)
{
return false;
}
/*
* Eratosthenes Test
*/
return isPrimeEratosthenes($int);
}
/**
* isPrimeEratosthenes()
*
* Checks if a given integer is a prime.
*
* @see http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes
*
* @input $int odd unsigned integer, bigger than 2
*
* @return bool
*/
function isPrimeEratosthenes($int)
{
$aryIsPrime = array();
for ($i = 3; $i <= $int; $i++)
{
if (($i % 2) == 0)
{
$aryIsPrime[$i] = false;
}
else
{
$aryIsPrime[$i] = true;
}
}
$i = 3;
while (($i * $i) <= $int)
{
if ($aryIsPrime[$i] === true)
{
$x = ($i * $i);
$y = $i;
while ($x <= $int)
{
if ($x == $int)
{
return false;
}
$aryIsPrime[$x] = false;
$y++;
$x = $y * $i;
}
}
$i++;
while ($aryIsPrime[$i] === false)
{
$i++;
}
}
return $aryIsPrime[$int];
}
// }}}
// {{{ main
list($int1aNum, $int1aDen) = split("/", float2fraction(INPUT_1A));
if (isPrime($int1aNum + $int1aDen))
{
$str1aIsPrime = "true";
}
else
{
$str1aIsPrime = "false";
}
list($int1bNum, $int1bDen) = split("/", reduceFraction(INPUT_1B_NUM, INPUT_1B_DEN));
if (isPrime($int1bNum + $int1bDen))
{
$str1bIsPrime = "true";
}
else
{
$str1bIsPrime = "false";
}
// }}}
// {{{ output
echo "Task 1 (a) - in: ". INPUT_1A ." - out: ". $int1aNum ."/". $int1aDen ." | Task 2 - in: ". ($int1aNum + $int1aDen) ." - out: ". $str1aIsPrime ."\n";
echo "Task 1 (b) - in: ". INPUT_1B_NUM ."/". INPUT_1B_DEN ." - out: ". reduceFraction(INPUT_1B_NUM, INPUT_1B_DEN) ." | Task 2 - in: ". ($int1bNum + $int1bDen) ." - out: ". $str1bIsPrime . "\n";
// }}}
?>
Thanks for the challenge, learnt alot.
Here's an entry with a couple of twists:
- it has it's own square root function
- it pickles the primes it finds for future runs of the program
It takes any number of values and evaluates them. You enter n to get that number's prime factors. n.n to change the decimal into a fraction and n/n to reduce the fraction.
Code:#!/usr/bin/python """ Weekly Programming Challenge: Friday, December 29, 2006 """ import os import cPickle import sys primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59] fn = 'Primes' fn_used = False org_p_cnt = len(primes) def sroot(x): a = float(x) / 4 b = x while int(a) != int(b): b = x / a a = (b + a) / 2 return int(a) + 1 def nth_prime(n): """ gets the next prime return number """ global primes global fn global fn_used global org_p_cnt while n >= len(primes): if fn_used: m = primes[-1] + 2 while not isprime(m): m += 2 primes.append(m) else: try: fn_used = True mpf = open(fn, 'rb') except IOError, e: print '*** ERROR *** Could not open %s for load.\ne = %s' % (fn, e) else: primes = cPickle.load(mpf) mpf.close() org_p_cnt = len(primes) print 'Using pickeled primes.' return primes[n] def isprime(n): """ tells if n is prime return boolean """ global primes if n < 2: return False if n in primes: return True limit = int(sroot(n)) + 1 i = 0 prime = 2 while True: if prime >= limit: return True if n % prime == 0: return False i += 1 prime = nth_prime(i) def pf(n): """ returns the prime factors of n return list """ a = [] if n < 0: n = -n a.append((-1, 1)) limit = sroot(n) i = 0 prime = 2 f_count = 0 while prime < limit: while n % prime == 0: n /= prime f_count += 1 if f_count > 0: a.append((prime, f_count)) limit = int(sroot(n)) + 1 f_count = 0 i += 1 prime = nth_prime(i) if n > 1: a.append((n, 1)) return a def reduce(n, d): """ reduces a fraction return tuple """ sign = 1 if n < 0: n = -n sign = -1 limit = sroot(min(n, d)) old_d = d i = 0 prime = 2 while limit > prime: while n % prime == 0 and d % prime == 0: n /= prime d /= prime if old_d != d: limit = sroot(min(n, d)) old_d = d i += 1 prime = nth_prime(i) return (sign*n, d) def ratio(a): """ Handles input strings with a '/' return tuple """ b = a.find('/') n = int(a[:b]) d = int(a[b+1:]) if d < 0: n = -n d = -d return reduce(n, d) def floater(x): """ converts x, a float into a ratio of integers return tuple """ k = len(x) - 1 i = x.find('.') return reduce(int(x[:i] + x[i+1:]), 10 ** (k-i)) def prt_lst(a, ans): """ prints the result """ n = ans[0] d = ans[1] if d == 1: print '%s = %d' % (a, n) else: print '%s = %d/%d' % (a, n, d) def do_input(a): """ handles an input string """ if a.find('.') >= 0: ans = floater(a) prt_lst(a, ans) x = sum(ans) if isprime(x): print '%d is prime' % (x) elif a.find('/') > 0: prt_lst(a, ratio(a)) elif a.isdigit(): x = int(a) ans = pf(x) if len(ans) == 1 and ans[0] == (x, 1): print '%d is prime' % (x) else: print '%s =' % (a), while ans: b = ans.pop(0) if b[1] > 1: print '%d^%d' % (b[0], b[1]), else: print b[0], if len(ans) > 0: print '*', print else: print "Can't process %s" % (a) if __name__ == '__main__': for s in sys.argv[1:]: do_input(s) if len(primes) > org_p_cnt: try: mpf = open(fn, 'w') except IOError, e: print '*** ERROR *** Could not open %s for dump.\ne = %s' % (fn, e) else: cPickle.dump(primes, mpf, 2) mpf.close() print 'Updated pickeled primes. %d primes added.' % (len(primes) - org_p_cnt)
Last edited by 56phil; January 11th, 2007 at 09:00 PM.
Regards,
56phil
Thanks for the kind words. I think ghostdog deserved to win though because I didn't do the prime test. This was because I was frantically trying to get an entry in before going skiing over new year and only had access to a ruby interpreter using an interactive online version, so didn't have the time to finish the challenge off which is a shame because it has been my favourite so far.
Now I'm back, I'm interested to read about a monthly challenge, but not sure how many contributions I could make (although just reading other entries is great in itself). Working together and in teams is also a good idea. I think we work together anyway by discussing each others' entries, but how would teams work? Would they be based on language? Team Ruby vs Team Python! That would be fun to see...
I've also been thinking that when testing for primes, you only need to test numbers of the form 6n + 1 and 6n -1 up to the square root of the number (because prime numbers are only of the form 6n + or - 1 and if there isn't a prime factor below the square root, there won't be one above it). This would cut down dramatically on the number of tests that needed doing.
DAZ
Bookmarks