Fast HCF Perl Code | Efficient GCD Algorithm Tutorial

Fast Perl Code to Find HCF (GCD)

This tutorial demonstrates an efficient Perl method to calculate the Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD). Using prime factorization and loop optimization, students can learn how Perl handles numerical sorting and divisor checks.
The H.C.F. code in Perl from the previous Finding HCF and GCD in Perl lesson could get a bit slowif we run into a prime number and this prime number becomes the loop range.
Now functions come in handy, don't they?

Let's see how we can fix this and make a fast Perl algorithm to find HCF:

Step 1:

Do a numerical sort on the resulting set so its first member is the smallest in the set.

Step 2:

Find the factors of the first number in the set.

Step 3:

Iteratively check through the set of numbers with the factors from Step 2 to make sure it is common to all.

Step 4:

For each common factor, divide every member of the number set by the common factor.

Note: You can comment out the Perl code for the main class from the previous lesson if you have been following.

So! Perl Fun Practice Exercise - Fast Find HCF

As a fun practice exercise, feel free to try out your own numbers, and see how the fast Perl code finds the HCF of those numbers.

Perl Code for Fast HCF - Module File.

package FASTHCF;

BEGIN {
    require Exporter;

    # for the sake of standard
    our $VERSION = 2016.12;

    # Inherit from exporter to export functions and variables
    our @ISA = qw(Exporter);

    # Functions and variables to be exported by default
    our @EXPORT_OK = qw(getHCF);
}

use warnings;
use strict;
use Carp qw(croak);

my ($index, $all_round_factor, $calc_result);
my (@set_of_numbers, @arg_copy, @common_factors, @minimal_prime_factors);

# simulate an object construct
# takes one argument  -- besides its package name;
# reference to set whose HCF is to found
sub new {
    no warnings;

    my $this = shift;
    my $parameters = {@_};
    bless $parameters, $this;
    $this->_init(@_);
    return $this;
}

# Simulate a constructor
sub _init {
    my $self = shift;

    my $tmp = shift;
    @common_factors = ();
    @set_of_numbers = @{$tmp};
    # STEP 1:
    @set_of_numbers = sort {$a <=> $b} @set_of_numbers;

    @arg_copy = @set_of_numbers;

    $index = 2;
    $all_round_factor = 0; # state flag
    $calc_result = 1;
}

# STEP 2:
# does the grunt work
# takes no arguments but requires '@set_of_numbers' to be set
sub findHCFFactors {
    while ($index < scalar @minimal_prime_factors) {
        $all_round_factor = 1;
        # STEP 3:
        for (0 .. $#set_of_numbers) {
            $all_round_factor = 0 if !($all_round_factor &&
                    $arg_copy[$_] % $minimal_prime_factors[$index] == 0);
        }
        # STEP 4:
        if ($all_round_factor) {
            $arg_copy[$_] /= $minimal_prime_factors[$index] for 0 .. $#set_of_numbers;
            push @common_factors, $minimal_prime_factors[$index];
        }
        $index++;
    }
    return;
}

# Returns a scalar value of the HCF
sub getHCF {
    require LISTPRIMEFACTORS or croak "Error $! occurred.";
    my $aux = LISTPRIMEFACTORS->new($set_of_numbers[0]);
    @minimal_prime_factors = @{$aux->onlyPrimeFactors()};

    $index = 0;
    findHCFFactors();

    #iterate through and retrieve members
    for (@common_factors) {
        $calc_result *= $_;
    }

    return $calc_result;
}

1;

Perl Code for Fast HCF - Main Class.

#!/usr/bin/perl;
use strict;
use warnings;
use FASTHCF qw(getHCF);

# Useful variables
my $answer;
my @set;

# Use the fast HCF module/class
@set = (20, 30, 40);
my $h_c_f = FASTHCF->new(\@set);
$answer = $h_c_f->getHCF();
print ("The H.C.F. of ", join(", ", @set), " is $answer\n");

print "\n\n";

I have a better version / See other versions.