Comments 55
берем кандидата (нечетного само собой), делим на все известные простые числа, меньшие чем половина кандидата.А почему не корень кандидата?
Зачем вычислять его каждый раз? Достаточно один раз запомнить его в переменной. А квадратный корень очень просто и быстро вычисляется бинарным поиском за логарифмическое время.
Так и есть, выйгрышь значительный.
Знаца, 16 нитей, мой ноутбук:
умножаем (knownPrime*2<candidate): 58.101
делим (knownPrime<candidate/2): 107.577
корень (knownPrima<sqrt(candidate)): 0.825
на графиках использовалось умножение
Знаца, 16 нитей, мой ноутбук:
умножаем (knownPrime*2<candidate): 58.101
делим (knownPrime<candidate/2): 107.577
корень (knownPrima<sqrt(candidate)): 0.825
на графиках использовалось умножение
пример кода можно? я на С только лабораторные в институте делал, боевых навыков не имею
а так, сам в шоке, думал где выход из цикла несанкционированный — нет, все честно
а так, сам в шоке, думал где выход из цикла несанкционированный — нет, все честно
В C# операции вроде *2, 4, 8… и деление на степени двойки оптимизированы.
В IL-коде еще будут операции умножения, а вот уже в ассемблерном после JIT будут только сдвиги. Однако в результирующем ASM для деления и умножения будет больше mov-ов.
C#
var j = i / 2;
IL:
L_0004: ldloc.0
L_0005: ldc.i4.2
L_0006: div
L_0007: stloc.1
ASM:
0000003f mov eax,dword ptr [rsp+20h]
00000043 cdq
00000044 sub eax,edx
00000046 sar eax,1
00000048 mov dword ptr [rsp+2Ch],eax
0000004c mov eax,dword ptr [rsp+2Ch]
00000050 mov dword ptr [rsp+24h],eax
C#:
var k = i >> 1;
IL:
L_0008: ldloc.0
L_0009: ldc.i4.1
L_000a: shr
L_000b: stloc.2
ASM:
00000054 mov eax,dword ptr [rsp+20h]
00000058 sar eax,1
0000005a mov dword ptr [rsp+28h],eax
В IL-коде еще будут операции умножения, а вот уже в ассемблерном после JIT будут только сдвиги. Однако в результирующем ASM для деления и умножения будет больше mov-ов.
C#
var j = i / 2;
IL:
L_0004: ldloc.0
L_0005: ldc.i4.2
L_0006: div
L_0007: stloc.1
ASM:
0000003f mov eax,dword ptr [rsp+20h]
00000043 cdq
00000044 sub eax,edx
00000046 sar eax,1
00000048 mov dword ptr [rsp+2Ch],eax
0000004c mov eax,dword ptr [rsp+2Ch]
00000050 mov dword ptr [rsp+24h],eax
C#:
var k = i >> 1;
IL:
L_0008: ldloc.0
L_0009: ldc.i4.1
L_000a: shr
L_000b: stloc.2
ASM:
00000054 mov eax,dword ptr [rsp+20h]
00000058 sar eax,1
0000005a mov dword ptr [rsp+28h],eax
Судя по этому коду
00000043 cdq
00000044 sub eax,edx
00000046 sar eax,1
у вас переменная — со знаком, поэтому возникает этот дополнительный код если сравнивать просто со сдвигом.
Но вот этой вот магии мне всё равно не понять:
00000048 mov dword ptr [rsp+2Ch],eax
0000004c mov eax,dword ptr [rsp+2Ch]
00000050 mov dword ptr [rsp+24h],eax
Кагбэ temp = eax; eax = temp; result = eax;
00000043 cdq
00000044 sub eax,edx
00000046 sar eax,1
у вас переменная — со знаком, поэтому возникает этот дополнительный код если сравнивать просто со сдвигом.
Но вот этой вот магии мне всё равно не понять:
00000048 mov dword ptr [rsp+2Ch],eax
0000004c mov eax,dword ptr [rsp+2Ch]
00000050 mov dword ptr [rsp+24h],eax
Кагбэ temp = eax; eax = temp; result = eax;
Да, магия странная. Сейчас проверил на Int64 вместо Int32, т.к запускаю у себя под 64-битной ОС. Никуда эти странные mov-ы не исчезли. Можно еще на досуге посмотреть, как JIT от Mono себя ведет в подобной ситуации.
Int64 i = 10;
0000003a mov qword ptr [rsp+20h],0Ah
Int64 j = i / 2;
00000043 mov rax,qword ptr [rsp+20h]
00000048 cqo
0000004a sub rax,rdx
0000004d sar rax,1
00000050 mov qword ptr [rsp+38h],rax
00000055 mov rax,qword ptr [rsp+38h]
0000005a mov qword ptr [rsp+28h],rax
Int64 k = i >> 1;
0000005f mov rax,qword ptr [rsp+20h]
00000064 sar rax,1
00000067 mov qword ptr [rsp+30h],rax
Int64 i = 10;
0000003a mov qword ptr [rsp+20h],0Ah
Int64 j = i / 2;
00000043 mov rax,qword ptr [rsp+20h]
00000048 cqo
0000004a sub rax,rdx
0000004d sar rax,1
00000050 mov qword ptr [rsp+38h],rax
00000055 mov rax,qword ptr [rsp+38h]
0000005a mov qword ptr [rsp+28h],rax
Int64 k = i >> 1;
0000005f mov rax,qword ptr [rsp+20h]
00000064 sar rax,1
00000067 mov qword ptr [rsp+30h],rax
Во-первых, если вычислять числа последовательно или почти последовательно (т.е. если количество чисел, обрабатываемых последовательно одним выч. узлом, сильно меньше, чем сами числа), то при переходе от n на n+m (где m сильно меньше n) корень легко пересчитывается: единичка либо прибавляется, либо нет :)
Во-вторых, в качестве альтернативы можно сравнивать p<=sqrt(n), а можно p*p<=n, и тут тоже можно придумать всякие оптимизации… ;)
Во-вторых, в качестве альтернативы можно сравнивать p<=sqrt(n), а можно p*p<=n, и тут тоже можно придумать всякие оптимизации… ;)
с точки зрения правильности алгоритма — абсолютно верно, с точки зрения оценки вычислительных мощностей — не существенно
на самом деле, вспомнил о квадрате, после того, как результаты для первого графика получил, соответственно, пришлось оставить неоптимальный алгоритм поиска, чтобы сравнение было верно
на самом деле, вспомнил о квадрате, после того, как результаты для первого графика получил, соответственно, пришлось оставить неоптимальный алгоритм поиска, чтобы сравнение было верно
Не думал, что мой ноутбук может серверную железяку переплюнуть.Кто-то, Вы или я, неправильно понимает графики. ПО оси абсцисс — время, т.е. «меньше-лучше». Графики Opteron'а в обоих случаях выше других, т.е. при равном количестве нитей, оптерону требуется большее время. Где «переплюв»?
А сам код не выложите?
Сейчас я укажу на недостатки к которым бы серьёзные дядечки придрались обязательно. (В универе пожурили бы и поставили хор., а вот
в исследовательском отделе коммерческой компании во все дырки бы…)
1. Непонятно что именно исследовалось.
В первом абзаце написано «нити»:
Тогда как в вариантах уже «процессы»:
Рекомендация: писать об этом явно и недвусмысленно, всегда показывать исходники тестов.
2. Непонятно что именно исследовалось. И, кажись, сам автор этого не понял.
2.1. Исследовалась ли качество реализации .Net framework в зависимости от архитектуры процессора?
2.2. Исследовалась ли скорость переключения в различных версиях .Net framework? (На висте минимальная версия 3.0, а на сервере какая
стояла?)
Рекомендация: исследовать на одной версии виртуальной машины. (Сначала 3.0, например, потом 3.5)
3. Непонятно что именно исследовалось. Автор этого сам не знает, и отсюда непонятные результаты.
в различных ОС.
В висте и получилось быстрее.
Рекомендация: исследовать на одной версии ОС.
Т.е. всё кроме исследуемого параметра должно быть одинаковым.
Заключение:
Автор — молодец, рекомендую продолжать, но только более вдумчиво.
в исследовательском отделе коммерческой компании во все дырки бы…)
1. Непонятно что именно исследовалось.
В первом абзаце написано «нити»:
в зависимости от количества нитей.
Тогда как в вариантах уже «процессы»:
Берем кандидата на простое число, отдаем его процессу, который его считает.
Берем кандидата,Т.е. нити или процессы? (Накладные расходы на создание процесса)
кормим бездельничающему процессу
Рекомендация: писать об этом явно и недвусмысленно, всегда показывать исходники тестов.
2. Непонятно что именно исследовалось. И, кажись, сам автор этого не понял.
2.1. Исследовалась ли качество реализации .Net framework в зависимости от архитектуры процессора?
2.2. Исследовалась ли скорость переключения в различных версиях .Net framework? (На висте минимальная версия 3.0, а на сервере какая
стояла?)
Рекомендация: исследовать на одной версии виртуальной машины. (Сначала 3.0, например, потом 3.5)
3. Непонятно что именно исследовалось. Автор этого сам не знает, и отсюда непонятные результаты.
Очень обескуражили результаты на AMD. Не думал, что мой ноутбук может серверную железяку переплюнуть. Может, есть тутА, по-моему, исследовалась как раз реализация механизма переключения
знатоки железа — поделитесь, в чем может быть дело?
в различных ОС.
В висте и получилось быстрее.
Рекомендация: исследовать на одной версии ОС.
Т.е. всё кроме исследуемого параметра должно быть одинаковым.
Заключение:
Автор — молодец, рекомендую продолжать, но только более вдумчиво.
За развернутый комментарии спасибо.
исследовалось то, как кол-во нитей или процессов (т.к. нет устоявшегося перевода), которые Thread, влияют на скорость вычисления, если не изменять базовый алгоритм.
ВМ я указал — везде одинаковая .Net 3.5.
Сравнивалось два подхода, т.е. сравнивать нужно функции на первом и втором графике для каждой из машин.
Разные машины приведены в общем-то для расширения кругозора (все равно они в стойках стоят и на праздниках бездельничают)
В любом случае — сравнение не в пользу АМД — серверный процессор от Интела тоже участвовал :)
исследовалось то, как кол-во нитей или процессов (т.к. нет устоявшегося перевода), которые Thread, влияют на скорость вычисления, если не изменять базовый алгоритм.
ВМ я указал — везде одинаковая .Net 3.5.
Сравнивалось два подхода, т.е. сравнивать нужно функции на первом и втором графике для каждой из машин.
Разные машины приведены в общем-то для расширения кругозора (все равно они в стойках стоят и на праздниках бездельничают)
В любом случае — сравнение не в пользу АМД — серверный процессор от Интела тоже участвовал :)
Еще бы через CUDA прогнать
Темой моей курсовой работы было «Реализация многопоточности в .Net». Хочу выложить на хабр, но не хватает кармы…
------простые числа на питоне--------------
#!/usr/bin/env python
import threading
thr = 100
sim = 10000
s = 3
S = [1,2]
def simple(n) :
for d in range(2,n) :
if n%d :
if d == n-1: S.append(n)
else : break
while s < sim :
if threading.activeCount() <= thr:
threading.Thread(target=simple, name="t%i" % s, args=[s]).start()
s += 1
print S
выполняется буквально несколько секунд на интеле 4 в debian
рад и удивлен))
Ну, несколько секунд для простых чисел до 10к — это как-то не очень быстро…
def good_prime©:
"""Возвращает список простых чисел, найденный
методом "решето Сундарама" """
#c=time.clock()
D=C/2
B=C/6
A=set(range(D))
for i in xrange(1,B+1):
for j in xrange(i,(D+i)/(1+2*i)+1):
A.discard(i+j+2*i*j)
A=[ 2*x+1 for x in A ]
#print time.clock()-c
return A
А так? :)
«Очень» оптимальная программа — много лишних итераций как в главном цикле, так и в функции.
1) в главном цикле можно перебирать только нечетные числа
2) в функции перебирать нечетные, от 3 до n/2 с шагом 2 ( d in range(3, n//2, 2) )
1) в главном цикле можно перебирать только нечетные числа
2) в функции перебирать нечетные, от 3 до n/2 с шагом 2 ( d in range(3, n//2, 2) )
Интересно было бы на Erlang посмотреть в такой же ситуации :) Не займетесь?
В данном случае выигрыша не будет. Скорее всего, Erlang будет медленнее из-за динамической типизации.
А вот не скажите. Все зависит от реализации. К тому же «динамический язык» не значит «медленный язык». Скажем, меня жутко удивило, что Dolphin Smalltalk считал некоторые тесты (кажется простые числа там тоже были) сопоставимо а то и быстрее альтернатив.
Хотя сами разработчики Dolphin-а говорят (и я с ними согласен) что целочисленные тесты для таких дел это зло и не могут являться критерием скорости языка. В том смысле, что реальные данные появляются в реальных же, боевых задачах, где автоматическая оптимизация кода скажет свое слово.
Хотя сами разработчики Dolphin-а говорят (и я с ними согласен) что целочисленные тесты для таких дел это зло и не могут являться критерием скорости языка. В том смысле, что реальные данные появляются в реальных же, боевых задачах, где автоматическая оптимизация кода скажет свое слово.
На той же википедии (на заметку)
За нахождение простого числа из более чем 108 десятичных цифр EFF назначила награду в 150000 долларов США.
Код в студию!
Код не выложили, Parallel Extensions навряд ли юзали, так что ядро вы использовали скорее всего одно. Хотелось бы видеть также результаты после использования NGen'а. Конфигурации серверов не указаны(интересует конкретные процессоры и оперативная память). На другие косяки вам тоже указали. В общем очень скользкий тест, который стоит провести более честно;)
Sign up to leave a comment.
Параллельные вычисления при поиске простых чисел.