function base_convert(number, frombase, tobase) {
// http://kevin.vanzonneveld.net
// + original by: Philippe Baumann
// * example 1: base_convert('A37334', 16, 2);
// * returns 1: '101000110111001100110100'
return parseInt(number+'', frombase+0).toString(tobase+0);
}
/*
CLASS FractionListObj
A fraction list object is instantiated with three pieces of data:
a numerator range, a denominator, and a number base.
PROPERTIES
public:
base: number base (defaults to 10).
fraction: list of fraction objects (FractionObj).
METHODS
PUBLIC __construct: Object constructor. Builds list of fraction objects.
PRIVATE parse: parses the numerator range and returns an array. This is
expected to be either one integer or else a starting and stopping integer.
*/
function FractionListObj(num, denom, base) {
// public base, fraction;
base = 1*base;
denom = 1*denom;
var numArray = parse(num);
var num1 = 1*numArray[0];
var num2 = 1*numArray[1];
if (num2 >= denom) { num2 = denom - 1; }
var base = base.length == 0 ? 10 : base;
if (base != 10) {
num1 = base_convert(num1, base, 10);
num2 = base_convert(num2, base, 10);
denom = base_convert(denom, base, 10);
}
this.fraction = [];
for (var i = num1; i <= num2; i++) {
this.fraction[i] = new FractionObj(i, denom, base);
}
this.formattedTable = buildHTMLTable(this.fraction);
function parse(n) {
var nrange = [];
var parts = n.split("-");
if (parts.length == 2) {
nrange.push(parts[0], parts[1]);
}
else {
nrange.push(n, n);
}
return nrange;
}
function buildHTMLTable(fractionList) {
var table = "
";
var headerRow =
" " +
" Fraction | " +
" Decimal | " +
" Length | " +
" Repeat | " +
" Palindromic | " +
"
";
var tableRows = [];
for (var rowData in fractionList) {
tableRows.push(
"" +
" " + fractionList[rowData].fraction + " | " +
" " + fractionList[rowData].decimal_data.decimal + " | " +
" " + fractionList[rowData].decimal_data.decimal_length + " | " +
" " + fractionList[rowData].decimal_data.repeating + " | " +
" " + fractionList[rowData].decimal_data.palindromic + " | " +
"
"
);
}
var formattedTable = table.replace("__HEADER__", headerRow);
formattedTable = formattedTable.replace("__ROWS__", tableRows.join(""));
return formattedTable;
}
}
/*
CLASS FractionObj
A fraction object is instantiated with three pieces of data: a numerator,
a denominator, and a number base.
PROPERTIES
private:
prime: array of prime numbers.
public:
num: numerator.
denom: denominator.
reduced_num: reduced numerator.
reduced_denom: reduced denominator.
base: number base.
fraction: fraction description.
section_list: list of sections in a decimal expansion. Sections are:
non-repeating, initial repeating portion, repeating portion complement.
decimal: decimal expansion.
decimal_places: number of decimal places in expansion.
repeating: number of repeating decimals in expansion.
For example, if the fraction is 1/6 (base 10):
num: 1
denom: 6
reduced_num: 1
reduced_denom: 6
base: 10
fraction: 1 / 6
decimal_places: 2
repeating: 1
decimal: .16
section_list: ('1', '6', '');
If the fraction is 3/6 (base 10):
num: 3
denom: 6
reduced_num: 1
reduced_denom: 2
base: 10
fraction: 3 / 6 (1 / 2)
decimal_places: 1
repeating: 0
decimal: .5
section_list: ('5', '', '');
If the fraction is 1/7 (base 10):
num: 1
denom: 7
reduced_num: 1
reduced_denom: 7
base: 10
fraction: 1 / 7
decimal_places: 6
repeating: 6
decimal: .142857
section_list: ('', '142', '857');
METHODS
PUBLIC __construct: Object constructor. Sets the public properties
directly, or else calls the methods that sets them.
PRIVATE calc_decimal: Calculate the decimal expansion for the specified
numerator, denominator, and base. Calculation is performed using long-
division, rather than relying on the computer's internal precision. In
this way, the calculation can be performed to far more decimal places than
otherwise possible.
PRIVATE count_non_repeating. Calculate and return the number of decimal
places that do not repeat, or -1 if the fraction resolves. The number of
non-repeating decimal places is calculated by comparing the denominator's
prime factors with those of the number base.
PRIVATE function get_gcf: Calculate and return the greatest common factor
of two integers.
*/
function FractionObj(num, denom, base) {
// public num, denom, reduced_num, reduced_denom, base, fraction, section_list, decimal, decimal_length, repeating;
var primes = [
-1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
];
var that = this;
this.num = num;
this.denom = denom;
gcf = get_gcf(num, denom); // GCF of numerator and denominator, for ensuring a reduced fraction.
var reduced_num = num / gcf;
var reduced_denom = denom / gcf;
var base = base;
if (reduced_denom < this.denom) {
this.fraction = this.num + " / " + this.denom + " (" + reduced_num + " / " + reduced_denom + ")";
}
else {
this.fraction = reduced_num + " / " + reduced_denom;
}
// calc_decimal sets three additional properties: decimal_length, repeating, and decimal.
this.decimal_data = calc_decimal();
function calc_decimal() {
// (Due to the complexity of the process, this method is copiously commented; hopefully this will clarify rather than obfuscate.)
// ----- BEGIN INITIALIZATION -----
// section_list is a list of the decimal expansion's sections; to be imploded at the end of the calc_decimal method.
// The possible sections are:
// non-repeating portion,
// initial repeating portion,
// repeating portion complement.
// Examples:
// 1/2 = .5. Non-repeating portion: 5; no repeating portions.
// 1/6 = .1666... Non-repeating portion: 1; initial repeating portion: 6; no repeating portion complement.
// 1/7 = .142857... No non-repeating potion; initial repeating portion: 142; repeating potion complement: 857.
var section_list = ['', '', ''];
var section_ndx = 0;
var palindromic;
// Call the count_non_repeating method to determine the number of non-repeating digits in the decimal expansion.
// If the fraction resolves (i.e., has no repeating portion), the count_non_repeating method returns -1.
var non_repeating = count_non_repeating();
// If a decimal expansion repeats, non_repeating_tally is used to detect the position at which the repetition begins.
// If there is no repetition, non_repeating_tally is set to one less than the denominator, which is a position at or beyond the decimal expansion's maximum possible length.
// Examples: 1/3 = .33333... The whole thing repeats, so non_repeating_tally is 0.
// 1/4 = .25 The fraction resolves. non_repeating_tally is one 3.
// 1/6 = .1666... Only the 6's repeat, so non_repeating_tally is 1.
var non_repeating_tally = non_repeating == -1 ? reduced_denom - 1 : non_repeating;
// The remainder_flag array contains one element for every possible remainder of a division involving the denominator. This means the number of elements is one less than the denominator.
var remainder_flag_list = [];
for (var i = 1; i < reduced_denom - 1; i++) {
remainder_flag_list[i] = false;
}
var repeating_decimal_flag = non_repeating != -1;
var start_repeat = 0;
var step_digit = 0;
var step_remainder = reduced_num;
var decimal_length = 0;
var linelength = 54;
// ----- END INITIALIZATION -----
// ----- BEGIN LONG DIVISION -----
// Continue the process as long as both of two conditions are true:
// a) there is a remainder,
// b) the current remainder (step_remainder) has not yet been encountered.
while (step_remainder != 0 && !remainder_flag_list[step_remainder]) {
// Mark the current remainder in the remainder flag list.
// While a decimal expansion can easily contain multiple instances of a certain digit, each possible remainder can occur only once.
// This means that if the process encounters a given remainder for a second time, it's begun to repeat itself; ergo, the process is finished.
remainder_flag_list[step_remainder] = true;
// This is where you add a zero to the number you're dividing and then see how many times the divisor goes into it.
// The number of times is called "step_digit" because, of course, this is the digit that results from this step of the process.
// The step_digits are concatenated at each step, so that the final string is the decimal expansion.
step_digit = Math.floor(step_remainder * base / reduced_denom);
// Check for the end of the non-repeating portion of the decimal.
if (decimal_length == non_repeating_tally) {
section_ndx++;
start_repeat = step_remainder; // Store this digit; it'll be used to determine when/if the complement begins.
}
// Append the current digit to the decimal expansion. Perform base conversion if not in base 10.
section_list[section_ndx] += (base != 10 ? base_convert(step_digit, 10, base) : step_digit);
// This is where you find the remainder in the current step of the division.
// Example: for 1/4, the first step would entail multiplying the 1 by 10 and determining how many times 4 divides the result. Since 4 goes into 10 twice,
// the "step_digit" value is 2. Since 10 - 8 is 2, the "step_remainder" value is 2.
step_remainder = step_remainder * base - step_digit * reduced_denom;
// Here's where we detect the repeating portion's complement.
// If in the course of calculating the decimal expansion one encounters two remainders whose sum is the denominator,
// then repeating portion can be split into two halves, and the sum of the two halves will be one less than an integer power of the number base.
// For instance, in base 10, 1/7 = .142857... The first remainder is 1 (the numerator), and the third remainder is 6. The two halves, 142 and 857,
// add up to 999, which is 10^3 - 1.
if (step_remainder + start_repeat == reduced_denom) {
section_ndx++;
}
decimal_length++;
// This just checks to see if the decimal expansion has more digits than we want to display on a single line. If so, an HTML line break is included.
if (decimal_length / linelength == Math.floor(decimal_length / linelength)) {
section_list[section_ndx] += '
';
}
}
// ----- END LONG DIVISION -----
// If the fraction evaluates to a repeating decimal, calculate the number of digits that repeat; otherwise, set it to 'None'.
repeating = repeating_decimal_flag ? decimal_length - non_repeating_tally : 'None';
// Decorate the sections (optional)
palindromic = section_list.join('').isPalindrome() ? 'Yes' : '';
section_list[0] = '' + section_list[0] + '';
section_list[1] = '' + section_list[1] + '';
section_list[2] = '' + section_list[2] + '';
// Set properties determined by this method.
var data = { "decimal_length" : decimal_length,
"repeating" : repeating,
"section_list" : section_list,
"decimal" : '.' + section_list.join(''),
"palindromic" : palindromic
};
return data;
}
function count_non_repeating() {
var base_factor_tally = 0;
var base_tmp = base;
var denom_tmp = reduced_denom;
var max_non_repeat_tally = 0;
var non_repeat_tally = 0;
var prime_ndx = 1;
var retval = 0;
// Loop through the prime number list, starting with 2 and continuing through the largest prime factor of the number base.
while (primes[prime_ndx] <= base_tmp) {
// non_repeat_tally must be initialized to 0 for each prime number in the cycle, so that the maximum tally can be determined.
non_repeat_tally = 0;
base_factor_tally = 0;
// First, tally the occurrences of the present prime number in the base's set of factors.
while (base_tmp / primes[prime_ndx] == Math.floor(base_tmp / primes[prime_ndx])) {
base_tmp /= primes[prime_ndx];
base_factor_tally++;
}
// If the present prime is indeed a factor of the base, process this block.
if (base_factor_tally > 0) {
// This block will determine the number of non-repeating decimal places generated for the current prime number. The maximum value from this will be returned.
prime_power = Math.pow(primes[prime_ndx], base_factor_tally);
// First, divide out all complete sets of the present prime number from the denominator, and tally the number of divisions.
while (denom_tmp / prime_power == Math.floor(denom_tmp / prime_power)) {
denom_tmp /= prime_power;
non_repeat_tally++;
}
// Second, check for any remaining instances of the prime number. If there are any, increment the tally, and divide out all that remain.
if (denom_tmp / primes[prime_ndx] == Math.floor(denom_tmp / primes[prime_ndx])) {
non_repeat_tally++;
while (denom_tmp / primes[prime_ndx] == Math.floor(denom_tmp / primes[prime_ndx])) {
denom_tmp /= primes[prime_ndx];
}
}
// Keep the max_non_repeat_tally up-to-date.
max_non_repeat_tally = Math.max(non_repeat_tally, max_non_repeat_tally);
}
prime_ndx++;
}
// If denom_tmp is equal to 1 at this point, the denominator's prime factors are all included in the set of factors for the base, which means the decimal resolves.
// If the denominator has no factors in common with the base, then there are no non-repeating digits.
retval = denom_tmp == 1 ? -1 : max_non_repeat_tally;
return retval;
}
function get_gcf(int1, int2) {
var ints = [int1, int2];
var finished = false;
while (!finished) {
ints = [Math.max(ints[0], ints[1]), Math.min(ints[0], ints[1])];
if (ints[0] / ints[1] == Math.floor(ints[0] / ints[1])) {
finished = true;
} else {
ints[0] = ints[0] - ints[1];
}
}
return ints[1];
}
}