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 = "__HEADER____ROWS__
"; 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]; } }