Weekly Programming Challenge: Friday, December 29, 2006

[Verminox]

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.

[eteran]

I'm surprised that there are no PHP entries... this would be really short and quick in PHP.

Here you go:

#!/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";

// }}}

?>

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.

Thanks for the challenge, learnt alot.

[56phil]

Here's an entry with a couple of twists:

1. it has it's own square root function
2. 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.

#!/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)

[daz4126]

Uptil now I liked the ruby implementation by daz4126 and ghostdog's python implementation the best...

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