среда, 10 сентября 2008 г.
вторник, 9 сентября 2008 г.
излог
- как быстрее всего пробежать стометровку?
- надо срезать.
практика показывает, что оптимизация единственный способ сделать что-либо вовремя.
- надо срезать.
практика показывает, что оптимизация единственный способ сделать что-либо вовремя.
Почему 9 не влияет на число при сложении
Числострадальцы любят складывать цифры до одной и делать из этого выводы.
Например 3378 => 3+3+7+8 => 6+15 => 6+1+5 => 12 => 3
Как это сделать быстро? Элементарно. Число 9 вобще не влияет на конечную сумму. То есть изымая 9 больше одной из обихода быстро находим что значит автомобильный номер попавшийся на глаза.
3378=> 1+2+1+2+7+8 => (2+7)+(1+8)+1+2 => 3
то есть дополняя циры до 9 сразу их отметаем. В итоге получаем один слой вычислений.
Например 3378 => 3+3+7+8 => 6+15 => 6+1+5 => 12 => 3
Как это сделать быстро? Элементарно. Число 9 вобще не влияет на конечную сумму. То есть изымая 9 больше одной из обихода быстро находим что значит автомобильный номер попавшийся на глаза.
3378=> 1+2+1+2+7+8 => (2+7)+(1+8)+1+2 => 3
то есть дополняя циры до 9 сразу их отметаем. В итоге получаем один слой вычислений.
Путаница
Как ответить на вопрос "Вы, не выходите?" одним словом да или нет.
И что это будет значить при этом выхожу я или нет.
И что это будет значить при этом выхожу я или нет.
Цепная цифровая реакция
Бесплатная электронная почта с двойным редиректом (на два адреса сразу)
может стать отличной спам машиной.
Создаём кольцо из бесплатных ящиков. А ящик с которого письмо может
быть отправлено на два цепляем на
a@a.a => b@b.b
b@b.b => c@c.c
c@c.c => d@d.d
c@c.c => e@e.e
d@d.d => a@a.a
e@e.e => a@a.a
любое письмо брошенное в данное кольцо через какое то время даст сумасшедший траффик.
не знаю, как оно в природе, но теоретически штука злобная.
может стать отличной спам машиной.
Создаём кольцо из бесплатных ящиков. А ящик с которого письмо может
быть отправлено на два цепляем на
a@a.a => b@b.b
b@b.b => c@c.c
c@c.c => d@d.d
c@c.c => e@e.e
d@d.d => a@a.a
e@e.e => a@a.a
любое письмо брошенное в данное кольцо через какое то время даст сумасшедший траффик.
не знаю, как оно в природе, но теоретически штука злобная.
Полиномиальная факторизация
Утверждение №1 - все множители числа N могут быть получены за 2*N операций сложения. То есть для полной факторизации любого натурального числа N нужно произвести 2*N операций сложения максимум.
Утверждение №2 - если известен минимально возможный остаток от деления числа N на любое M меньшее N и соответсвующие кратные K , то получение минимально возможного остатка от деления N на M-1 занимает четыре операции сложения максимум.
Попробую обосновать данные утверждения:
Возьмём выражение N=M*K+R
1) Проведём элементарное преобразование
N = M*K+R = (M-1)*K + (R+K)
2) В случае, если R+K>=M-1 существует остаток R1 меньший R такой, что
N = (M-1)*K + (M-1)*L + R1 то есть
N = (M-1)*(K+L) + R1
в случае, если получен R1 такой, что R1+(K+L)>=M-1 то R1 минимальный
остаток от деления N на M-1. Частное в данном случае будет равно K+L
3) Получение числа L может быть получено инкрементально путём увеличения
на каждом шаге K на единицу и определения R1 вычитая из него M-1
это возможно из тождества N = (M-1)*(K+1) + (R1 - (M-1))
4) Утверждение полученное эмпирически.
Если R минимальный остаток от деления числа N на M и K, то если R+K>=M-1
существует один остаток R1 и он будет единственным минимальным остатком такой что
N = (M-1)*(K+L) + R1 где L натуральное число. В случае же, если R+K<M-1 то новый минимальный остаток будет равен R+K для тождества N = (M-1)*K + (R+K) 5)
5) Частный случай, когда R1=0 - случай когда R делится нацело на M-1. частное в данном случае находится автоматически.
6) Сложность алгоритма. Количество шагов за которые может быть найдено решение будет существенно меньше чем N*((N/2)-SQRT(N)) (далее будет показано насколько меньше).
7) По вышеизложенным выкладкам построим элементарный алгоритм:
procedure TForm1.Button1Click(Sender: TObject);
var
Source : TNumber;
Index : TNumber;
Shift : TNumber;
Candidat : TNumber;
begin
Source:=strtoint(Edit1.text); // Source Number
Index:=2;
Candidat:=Trunc(Source/Index);
Shift:=Source-Candidat*Index;
if (Shift=0) then begin
Memo1.Lines.Add(inttostr(Candidat)+';'+inttostr(Index)); // Result
end;
while (Candidat>SQRT(Source)) do begin
if (Candidat>Shift) then begin
dec(Candidat);
Shift:=Shift+Index;
end
else begin
inc(Index);
Shift:=Abs(Candidat-Shift);
if (Shift=0) then& nbsp;begin
Memo1.Lines.Add(inttostr(Candidat)+';'+inttostr(Index)); // Result
end; // if
end; // if
end; // while
end; // procedure
* Алгоритм только иллюстрирует процесс
8) И посчитаем (в лоб) количество операций которое понадобится для получения всех делителей.
Первая колонка - исходное число. Вторая - количество операций для полной факторизации. Третья величина (N/2)*SQRT(N). Опытным путём было получено, что для полной факторизации числа нужно 2*N операций.
Итоги:
1) Был построен алгоритм получающий на каждом шаге минимально возможный остаток
2) В случае, когда минимально возможный остаток равен нулю мы имеем случай деления нацело. То есть алгоритм производит факторизацию исходного числа - получение делителей числа.
3) Численно было получено число операций, необходимых для полной факторизации числа. Для исходного числа N число операций сложения для факторизации числа будет 2*N
Википедия утверждает, что для больших N полиномиальная сложность хороша при факторизации. В приведённом решении, сложность не просто полиномиальна - она линейна. Для случаев RSA когда исходное число - произведение двух простых чисел Задача сразу упрощается, потому что на каждом шаге мы получаем сразу два делителя M и L. Что особенно ценно в данном алгоритме - в центральной части алгоритма используется только операция сложения(она де сравнение и вычитание). Нет деления и умножения. Алгоритм детерминирован. Время работы может быть рассчитано заранее.
Утверждение №2 - если известен минимально возможный остаток от деления числа N на любое M меньшее N и соответсвующие кратные K , то получение минимально возможного остатка от деления N на M-1 занимает четыре операции сложения максимум.
Попробую обосновать данные утверждения:
Возьмём выражение N=M*K+R
1) Проведём элементарное преобразование
N = M*K+R = (M-1)*K + (R+K)
2) В случае, если R+K>=M-1 существует остаток R1 меньший R такой, что
N = (M-1)*K + (M-1)*L + R1 то есть
N = (M-1)*(K+L) + R1
в случае, если получен R1 такой, что R1+(K+L)>=M-1 то R1 минимальный
остаток от деления N на M-1. Частное в данном случае будет равно K+L
3) Получение числа L может быть получено инкрементально путём увеличения
на каждом шаге K на единицу и определения R1 вычитая из него M-1
это возможно из тождества N = (M-1)*(K+1) + (R1 - (M-1))
4) Утверждение полученное эмпирически.
Если R минимальный остаток от деления числа N на M и K, то если R+K>=M-1
существует один остаток R1 и он будет единственным минимальным остатком такой что
N = (M-1)*(K+L) + R1 где L натуральное число. В случае же, если R+K<M-1 то новый минимальный остаток будет равен R+K для тождества N = (M-1)*K + (R+K) 5)
5) Частный случай, когда R1=0 - случай когда R делится нацело на M-1. частное в данном случае находится автоматически.
6) Сложность алгоритма. Количество шагов за которые может быть найдено решение будет существенно меньше чем N*((N/2)-SQRT(N)) (далее будет показано насколько меньше).
7) По вышеизложенным выкладкам построим элементарный алгоритм:
procedure TForm1.Button1Click(Sender: TObject);
var
Source : TNumber;
Index : TNumber;
Shift : TNumber;
Candidat : TNumber;
begin
Source:=strtoint(Edit1.text); // Source Number
Index:=2;
Candidat:=Trunc(Source/Index);
Shift:=Source-Candidat*Index;
if (Shift=0) then begin
Memo1.Lines.Add(inttostr(Candidat)+';'+inttostr(Index)); // Result
end;
while (Candidat>SQRT(Source)) do begin
if (Candidat>Shift) then begin
dec(Candidat);
Shift:=Shift+Index;
end
else begin
inc(Index);
Shift:=Abs(Candidat-Shift);
if (Shift=0) then& nbsp;begin
Memo1.Lines.Add(inttostr(Candidat)+';'+inttostr(Index)); // Result
end; // if
end; // if
end; // while
end; // procedure
* Алгоритм только иллюстрирует процесс
8) И посчитаем (в лоб) количество операций которое понадобится для получения всех делителей.
54;106;1061999999997;1999999987;499968374223540623
55;105;1105
56;115;1149
57;105;1194
58;108;1240
59;108;1287
60;116;1335
61;112;1384
1671;3333;1327814
1672;3342;1329424
1673;3337;1331035
1674;3346;1332647
1675;3342;1334260
1676;3345;1335874
1677;3347;1337489
4161;8315;8388552
4162;8316;8392617
4163;8317;8396682
4164;8324;8400749
4165;8325;8404817
4166;8324;8408885
4167;8326;8412955
4168;8330;8417026
4169;8329;8421097
4170;8338;8425170
10923;21839;58514367
10924;21841;58525134
10925;21845;58535902
10926;21848;58546670
10927;21846;58557440
10928;21851;58568211
10929;21849;58578983
26957;53909;358913966
26958;53914;358940677
26959;53912;358967389
26960;53924;358994103
26961;53923;359020817
26962;53926;359047532
26963;53921;359074248
77982;155966;3018819488
77983;155960;3018897051
77984;155968;3018974616
77985;155969;3019052182
77986;155968;3019129748
77987;155971;3019207316
77988;155982;3019284884
77989;155973;3019362454
77990;155982;3019440025
77991;155977;3019517596
77992;155982;3019595169
77993;155981;3019672742
77994;155994;3019750317
77995;155987;3019827893
77996;155998;3019905469
77997;155989;3019983047
1150521;2301035;660615209951
1150522;2301036;660616358864
1150523;2301037;660617507777
1150524;2301068;660618656692
1150525;2301042;660619805608
1150526;2301058;660620954524
1150527;2301047;660622103442
1150528;2301053;660623252360
99999997;199999985;4998999700045004
Первая колонка - исходное число. Вторая - количество операций для полной факторизации. Третья величина (N/2)*SQRT(N). Опытным путём было получено, что для полной факторизации числа нужно 2*N операций.
Итоги:
1) Был построен алгоритм получающий на каждом шаге минимально возможный остаток
2) В случае, когда минимально возможный остаток равен нулю мы имеем случай деления нацело. То есть алгоритм производит факторизацию исходного числа - получение делителей числа.
3) Численно было получено число операций, необходимых для полной факторизации числа. Для исходного числа N число операций сложения для факторизации числа будет 2*N
Википедия утверждает, что для больших N полиномиальная сложность хороша при факторизации. В приведённом решении, сложность не просто полиномиальна - она линейна. Для случаев RSA когда исходное число - произведение двух простых чисел Задача сразу упрощается, потому что на каждом шаге мы получаем сразу два делителя M и L. Что особенно ценно в данном алгоритме - в центральной части алгоритма используется только операция сложения(она де сравнение и вычитание). Нет деления и умножения. Алгоритм детерминирован. Время работы может быть рассчитано заранее.
Подписаться на:
Сообщения (Atom)