Newton’s Method and Perl Formats: The Weekly Challenge 105

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1

You are given positive numbers $N and $k. Write a script to find out the $Nth root of $k


use strict;
use warnings;
sub nth_root{
    my($n, $k) = @_;
    my $x_i = int(rand(10) + 1); 
    my $r;
    for my $i (0 .. 100){
        $x_i = (1 / $n) * (($n - 1) * $x_i + ($k / $x_i ** ($n - 1)));  
    return $x_i;  

    my($N, $k);
    $N = 5;
    $k = 248832;
    print nth_root($N, $k) . "\n";
    $N = 5;
    $k = 34;
    print sprintf("%0.2f", nth_root($N, $k)) . "\n";

Sample Run

$ perl perl/ch-1.pl


One of my neatest things one can learn in calculus class, I would argue, is Newton’s method for computing square roots. One can read more on this elsewhere but this works by using a recurrence relationship, defined using directives, to compute the zero of a function. If the function is x^n - a, the zero we are computing is the nth root of a.

To start the process any x_0 may be chosen. Here we pick an integer from 1 to 10 at random.

You can compute this for as many iterations as you’d like, of course, but here even 100 iterations is much more than enough to properly converge.

Part 2

You are given a $name. Write a script to display the lyrics to the Shirley Ellis song The Name Game.


use strict;
use warnings;

sub name_game{
    my($name) = @_;
    my($b, $f, $m); 
    my $first_letter = lc(substr($name, 0, 1));
    my $irregular_v = $first_letter =~ tr/aeiou//d;
    my $irregular_bfm = $first_letter =~ tr/bfm//d;
    unless($irregular_v || $irregular_bfm){
        $b = "b" . lc(substr($name, 1)); 
        $f = "f" . lc(substr($name, 1)); 
        $m = "m" . lc(substr($name, 1)); 
        $b = "b" . lc($name);
        $f = "f" . lc($name); 
        $m = "m" . lc($name); 
        $b = "b" . lc(substr($name, 1)); 
        $f = "f" . lc(substr($name, 1)); 
        $m = "m" . lc(substr($name, 1)); 
        $b = lc(substr($name, 1)) if lc(substr($name, 0, 1)) eq "b"; 
        $f = lc(substr($name, 1)) if lc(substr($name, 0, 1)) eq "f"; 
        $m = lc(substr($name, 1)) if lc(substr($name, 0, 1)) eq "m"; 
    format NAME_GAME = 
        @*, @*, bo-@* 
        $name, $name, $b 
        Banana-fana fo-@* 
    $~ = "NAME_GAME";

    $name = "Katie";  
    print "\n"; 
    $name = "Adam";  
    print "\n"; 
    $name = "Mary";  

Sample Run

$ perl perl/ch-2.pl
        Katie, Katie, bo-batie
        Banana-fana fo-fatie

        Adam, Adam, bo-badam
        Banana-fana fo-fadam

        Mary, Mary, bo-bary
        Banana-fana fo-fary


My first comment is that I am a terrible singer and have never been able to reliably remember songs with rules like this at all, at any time of my life! Practically speaking that means I may have had to do more research on this part than one might expect. I did find an excellent reference (listed below) which detailed the rules for each case very clearly.

Perhaps the trickiest case in the one in which the name starts with a b, f, or m. For these you need to adjust the one specific rewrite rule which uses that letter. In the example above we see that Mary requires special handling and becomes Fee-fi-mo-ary.

To print the verses out I use a Perl Format. Formats are not the most commonly used feature of Perl these days but still have some nice uses such as here where we want to define a simple template for plain text output. Formats can even be used to write to files, but here we just print to the console.

One Format trick which I have not used before is the use of a variable width field. Much of the documentation for Formats has to do with fixed width fields which can be centered, padded left, padded right, involve multiple lines, and so forth. A common case which is not typically well explained is one we need here. Names are of different lengths and may be followed by a comma or an exclamation point. Padding right adds unwanted space before the “,” or “!”. Padding left adds unwanted space before the name. Centering does both! The trick is to use @* for the field specifier in the Format definition. This will allow the value to be substituted in without any padding.


Challenge 105

nth root by Newton’s method

Name Game Rules

Perl Formats

posted at: 11:28 by: Adam Russell | path: /perl | permanent link to this entry