“Приблизительный” наибольший общий делитель
Я написал эту небольшую функцию несколько лет назад:
function sqlvprintf($query, $args)
{
global $DB_LINK;
$ctr = 0;
ensureConnection(); // Connect to database if not connected already.
$values = array();
foreach ($args as $value)
{
if (is_string($value))
{
$value = "'" . mysqli_real_escape_string($DB_LINK, $value) . "'";
}
else if (is_null($value))
{
$value = 'NULL';
}
else if (!is_int($value) && !is_float($value))
{
die('Only numeric, string, array and NULL arguments allowed in a query. Argument '.($ctr+1).' is not a basic type, it\'s type is '. gettype($value). '.');
}
$values[] = $value;
$ctr++;
}
$query = preg_replace_callback(
'/{(\\d+)}/',
function($match) use ($values)
{
if (isset($values[$match[1]]))
{
return $values[$match[1]];
}
else
{
return $match[0];
}
},
$query
);
return $query;
}
function runEscapedQuery($preparedQuery /*, ...*/)
{
$params = array_slice(func_get_args(), 1);
$results = runQuery(sqlvprintf($preparedQuery, $params)); // Run query and fetch results.
return $results;
}
Это позволяет запускать операторы в однострочном C # -ish String.Format, например:
runEscapedQuery("INSERT INTO Whatever (id, foo, bar) VALUES ({0}, {1}, {2})", $numericVar, $stringVar1, $stringVar2);
Он избегает использования типа переменной. Если вы попытаетесь параметризовать имена таблиц и столбцов, это будет терпеть неудачу, поскольку она помещает каждую строку в кавычки, которая является недопустимым синтаксисом.
ОБНОВЛЕНИЕ БЕЗОПАСНОСТИ: предыдущая версия str_replace разрешала инъекции, добавляя токены {#} в пользовательские данные. Эта версия preg_replace_callback не вызывает проблем, если замена содержит эти токены.
6 ответов
Можно выполнить алгоритм GCD Euclid с чем-либо меньшим тогда 0.01 (или небольшое число по Вашему выбору) быть псевдо 0. С Вашими числами:
3.700 = 1 * 2.468 + 1.232,
2.468 = 2 * 1.232 + 0.004.
, Таким образом, псевдо GCD первых двух чисел 1.232. Теперь Вы берете GCD этого с Вашим последним числом:
6.1699 = 5 * 1.232 + 0.0099.
Так 1.232 псевдо GCD, и mutiples 2,3,5. Для улучшения этого результата можно взять линейную регрессию на точках данных:
(2,2.468), (3,3.7), (5,6.1699).
наклон является улучшенным псевдо GCD
Протест: первая часть этого является алгоритмом, численно нестабильно - если Вы запускаете с очень грязных данных, Вы в беде.
Это напоминает мне о проблеме нахождения хороших приближений рационального числа вещественных чисел. Стандартная техника является расширением непрерывной дроби:
def rationalizations(x):
assert 0 <= x
ix = int(x)
yield ix, 1
if x == ix: return
for numer, denom in rationalizations(1.0/(x-ix)):
yield denom + ix * numer, numer
Мы могли применить это непосредственно к подходу Jonathan Leffler и Sparr:
>>> a, b, c = 2.468, 3.700, 6.1699
>>> b/a, c/a
(1.4991896272285252, 2.4999594813614263)
>>> list(itertools.islice(rationalizations(b/a), 3))
[(1, 1), (3, 2), (925, 617)]
>>> list(itertools.islice(rationalizations(c/a), 3))
[(2, 1), (5, 2), (30847, 12339)]
собирание первого достаточно хорошего приближения от каждой последовательности. (3/2 и 5/2 здесь.) Или вместо того, чтобы непосредственно сравнить 3.0/2.0 с 1,499189..., Вы могли заметить, чем использование 925/617 намного больше целые числа, чем 3/2, делая 3/2 превосходное место для остановки.
Это должно не очень иметь значение, на какое из чисел Вы делитесь. (Используя a/b и c/b Вы получаете 2/3 и 5/3, например.), После того как у Вас есть целочисленные отношения, Вы могли совершенствовать подразумеваемую оценку фундаментальной линейной регрессии shsmurfy's использования. Все побеждают!
Выразите свои измерения как кратные числа самого низкого. Таким образом Ваш список становится 1.00000, 1.49919, 2.49996. Дробные части этих значений будут очень близко к 1/Nths для некоторого значения N, продиктованного тем, как близко Ваше самое низкое значение к основной частоте. Я предложил бы цикличное выполнение посредством увеличения N, пока Вы не находите достаточно усовершенствованное соответствие. В этом случае, для N=1 (то есть, принимая X=2.468 Ваша основная частота) Вы нашли бы стандартное отклонение 0,3333 (два из трех значений.5 прочь X * 1), который неприемлемо высок. Для N=2 (то есть, принимая 2.468/2 Ваша основная частота) Вы нашли бы стандартное отклонение фактически нуля (все три значения в.001 из нескольких X/2), таким образом 2.468/2 является Вашим приблизительным GCD.
главный дефект в моем плане - то, что он работает лучше всего, когда самое низкое измерение является самым точным, который вероятен не случай. Это могло быть смягчено путем выполнения всей операции многократно, отбрасывания самого низкого значения в списке измерений каждый раз, затем использовать список результатов каждой передачи определить более точный результат. Другой способ уточнить результаты был бы, корректируют GCD для уменьшения стандартного отклонения между целочисленными кратными числами GCD и измеренных значений.
Интересный вопрос... не легкий.
я предполагаю, что посмотрел бы на отношения демонстрационных значений:
- 3.700 / 2.468 = 1.499...
- 6.1699 / 2.468 = 2.4999...
- 6.1699 / 3.700 = 1.6675...
И я тогда искал бы простое отношение целых чисел в тех результатах.
- 1,499 ~ = 3/2
- 2.4999 ~ = 5/2
- 1.6675 ~ = 5/3
я не преследовал его через, но где-нибудь вдоль строки, Вы решаете, что ошибка 1:1000 или что-то достаточно хорошо, и Вы отслеживаете в обратном порядке для нахождения основного приблизительного GCD.
Я предполагаю, что все Ваши числа являются кратными числами [1 112] целое число значения. Для остальной части моего объяснения A обозначит "корневую" частоту, которую Вы пытаетесь найти, и B будет массивом чисел, с которых необходимо запустить.
то, Что Вы пытаетесь сделать, поверхностно подобно линейная регрессия . Вы пытаетесь найти линейную модель y=mx+b, который минимизирует среднее расстояние между линейной моделью и рядом данных. В Вашем случае, b=0, m является корневой частотой, и y представляет данные значения. Самая большая проблема состоит в том, что независимые переменные X не явно заданы. Единственная вещь мы знаем приблизительно X, состоит в том, что все ее участники должны быть целыми числами.
Ваша первая задача пытается определить эти независимые переменные. Лучший метод, о котором я могу думать в данный момент, предполагает, что данные частоты имеют почти последовательные индексы (x_1=x_0+n). Так B_0/B_1=(x_0)/(x_0+n), учитывая (надо надеяться), маленькое целое число n. Можно тогда использовать в своих интересах то, что x_0 = n/(B_1-B_0), запустите с n=1 и продолжайте углублять его вплоть до k-rnd (k), в определенном пороге. После того, как у Вас будет x_0 (начальный индекс), можно приблизить корневую частоту (A = B_0/x_0). Тогда можно приблизить другие индексы путем нахождения x_n = rnd(B_n/A). Этот метод не очень устойчив и вероятно перестанет работать, если ошибка в данных является большой.
, Если Вы хотите лучшее приближение корневой частоты A, можно использовать линейную регрессию для уменьшения ошибки линейной модели теперь, когда у Вас есть соответствующие зависимые переменные. Самый легкий метод, чтобы сделать так выравнивание методом наименьших квадратов использования. Mathworld Вольфрама имеет всестороннюю математическую обработку проблемы, но довольно простое объяснение может быть найдено с некоторым гуглением.
Решение, которое я видел и использовал сам, состоит в том, чтобы выбрать некоторую константу, сказать 1000, умножить все числа на эту константу, вокруг них к целым числам, найти GCD этих целых чисел с помощью стандартного алгоритма и затем разделить результат на упомянутую константу (1000). Чем больше константа, тем выше точность.