Как можно оптимизировать алгоритм сокращения дроби?

Question

[Umid]

Добрый день.

Решил сокращать дроби, деля их на простые числа от 2 до минимального значения между числителем и знаменателем (т.е. если числитель больше знаменателя, то берём все простые числа от 2 до знаменателя, и наоборот).
Нахождение простых чисел реализовал через "Решето Эратосфена". Все найденные простые числа остаются в массиве simpleNumbers, в целях оптимизации, т.к. функция сокращения дроби используется многократно.

var simpleNumbers = [2, 3];
function getSimpleNumbers(limit) {
	var i = (simpleNumbers.length == 0) ? 0 : simpleNumbers[ simpleNumbers.length - 1 ];

	if( i > limit ) {
		for (var k = 0; ; k++) {
			if( simpleNumbers[k] > limit ) {
				return simpleNumbers.slice(0, k);
				break;
			}
		}
	}

	for (; i <= limit; i++) {
		var flag = true;

		for (var j = 0; j < simpleNumbers.length; j++) {
			if( i % simpleNumbers[j] == 0 ) {
				flag = false;
				break;
			}			
		}		
		if( flag ) {
			simpleNumbers.push(i);
		}
	}


	return simpleNumbers;
}

// Функция принимает два аргумента и максимально сокращает их. 
// Функция возвращает объект с двумя свойствами n и d (числитель и знаменатель)
function reduceFrac(numerator, denomerator) {
	var frac = {
		n: numerator,
		d: denomerator
	}, s;

	if(Math.abs(frac.n) > Math.abs(frac.d)) {
		s = getSimpleNumbers( Math.abs(frac.d) );
	} else {
		s = getSimpleNumbers( Math.abs(frac.n) );
	}

	for (var i = 0; i < s.length; i++) {
		while(true) {
			if( Math.abs(frac.n % s[i]) == 0 && Math.abs(frac.d % s[i]) == 0 ) {
				frac.n /= s[i];
				frac.d /= s[i];
			} else {
				break;
			}
		}
	}
	return frac;
}

Answer 1

[Rsa97]

Бинарный алгоритм вычисления наибольшего общего делителя (НОД)

function nod(m, n) {
  var mult = 0;
  while (true) {
    if (0 == m) {
      return n << mult;
    }
    if (0 == n) {
      return m << mult;
    }
    if (1 == m || 1 == n) {
      return 1 << mult;
    }
    if (m == n) {
      return m << mult;
    }
    if (0 == (m & 1) && 0 == (n & 1)) {
      mult++;
      m >>= 1;
      n >>= 1;
    } else if (0 == (m & 1)) {
      m >>= 1;
    } else if (0 == (n & 1)) {
      n >>= 1;
    } else if (m > n) {
      m = (m-n) >> 1;
    } else {
      n = (n-m) >> 1;
    }
  }
}

function reduceFrac(numerator, denomerator) {
  var divider = nod(numerator, denomerator);
  return {n: numerator/divider, d: denomerator/divider};
}

Comments

[Umid]

Очень круто. Спасибо.

В общем погуглил про левый сдвиг и "Бинарный алгоритм вычисления наибольшего общего делителя". Но никак не смог понять, для чего здесь нужен левый сдвиг.
Полностью понимаю, как он работает, но связь уловить не могу.

[Rsa97]

Umid, Левый сдвиг на 1 эквивалентен умножению на 2.
Если m и n чётные, то nod(m, n) = 2*nod(m/2, n/2)
Вместо накопления множителя можно накапливать сдвиг.

[longclaps]

Rsa97, вообще дикий оверкил, довольно простого Эвклида:

function reduceFrac(numerator, denomerator) {
    let a = numerator, b = denomerator;
    while (a) {
        let c = b % a;
        b = a;
        a = c;
    }
    return [numerator / b, denomerator / b]
}

Если внутреннее представление целых в js - 32разрядное, худшее, что может прийти на вход - пара (1836311903, 1134903170), это два соседних числа Фибоначчи, меньших 0x7FFFFFFF.
Тогда что обычный эвклид проведёт 44 итерации, что этот (тоже 44). Ну а цена что деления с остатком, что вычитания можно считать одинакова.
Так что эти ухищрения полезны лишь в длинной арифметике.

[Umid]

longclaps, Ого, спасибо.

Answer 2

[jcmvbkbc]

Классическое решение -- поиск НОД алгоритмом Евклида.