Comments 55
берем кандидата (нечетного само собой), делим на все известные простые числа, меньшие чем половина кандидата.А почему не корень кандидата?
+2
UFO just landed and posted this here
Зачем вычислять его каждый раз? Достаточно один раз запомнить его в переменной. А квадратный корень очень просто и быстро вычисляется бинарным поиском за логарифмическое время.
+1
UFO just landed and posted this here
Так и есть, выйгрышь значительный.
Знаца, 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
на графиках использовалось умножение
0
UFO just landed and posted this here
пример кода можно? я на С только лабораторные в институте делал, боевых навыков не имею
а так, сам в шоке, думал где выход из цикла несанкционированный — нет, все честно
а так, сам в шоке, думал где выход из цикла несанкционированный — нет, все честно
0
UFO just landed and posted this here
UFO just landed and posted this here
В 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
+7
Судя по этому коду
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;
+1
Да, магия странная. Сейчас проверил на 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
0
Во-первых, если вычислять числа последовательно или почти последовательно (т.е. если количество чисел, обрабатываемых последовательно одним выч. узлом, сильно меньше, чем сами числа), то при переходе от n на n+m (где m сильно меньше n) корень легко пересчитывается: единичка либо прибавляется, либо нет :)
Во-вторых, в качестве альтернативы можно сравнивать p<=sqrt(n), а можно p*p<=n, и тут тоже можно придумать всякие оптимизации… ;)
Во-вторых, в качестве альтернативы можно сравнивать p<=sqrt(n), а можно p*p<=n, и тут тоже можно придумать всякие оптимизации… ;)
0
с точки зрения правильности алгоритма — абсолютно верно, с точки зрения оценки вычислительных мощностей — не существенно
на самом деле, вспомнил о квадрате, после того, как результаты для первого графика получил, соответственно, пришлось оставить неоптимальный алгоритм поиска, чтобы сравнение было верно
на самом деле, вспомнил о квадрате, после того, как результаты для первого графика получил, соответственно, пришлось оставить неоптимальный алгоритм поиска, чтобы сравнение было верно
0
Не думал, что мой ноутбук может серверную железяку переплюнуть.Кто-то, Вы или я, неправильно понимает графики. ПО оси абсцисс — время, т.е. «меньше-лучше». Графики Opteron'а в обоих случаях выше других, т.е. при равном количестве нитей, оптерону требуется большее время. Где «переплюв»?
0
ноутбук на коре дуо. Оптерон серверная железка.
0
*По оси абсцисс…
0
А сам код не выложите?
0
если общественность интересует — выложу, выкладывать быдло код не хочется, а приводить его в порядок просто так — лень
+1
UFO just landed and posted this here
Сейчас я укажу на недостатки к которым бы серьёзные дядечки придрались обязательно. (В универе пожурили бы и поставили хор., а вот
в исследовательском отделе коммерческой компании во все дырки бы…)
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. Не думал, что мой ноутбук может серверную железяку переплюнуть. Может, есть тутА, по-моему, исследовалась как раз реализация механизма переключения
знатоки железа — поделитесь, в чем может быть дело?
в различных ОС.
В висте и получилось быстрее.
Рекомендация: исследовать на одной версии ОС.
Т.е. всё кроме исследуемого параметра должно быть одинаковым.
Заключение:
Автор — молодец, рекомендую продолжать, но только более вдумчиво.
+11
За развернутый комментарии спасибо.
исследовалось то, как кол-во нитей или процессов (т.к. нет устоявшегося перевода), которые Thread, влияют на скорость вычисления, если не изменять базовый алгоритм.
ВМ я указал — везде одинаковая .Net 3.5.
Сравнивалось два подхода, т.е. сравнивать нужно функции на первом и втором графике для каждой из машин.
Разные машины приведены в общем-то для расширения кругозора (все равно они в стойках стоят и на праздниках бездельничают)
В любом случае — сравнение не в пользу АМД — серверный процессор от Интела тоже участвовал :)
исследовалось то, как кол-во нитей или процессов (т.к. нет устоявшегося перевода), которые Thread, влияют на скорость вычисления, если не изменять базовый алгоритм.
ВМ я указал — везде одинаковая .Net 3.5.
Сравнивалось два подхода, т.е. сравнивать нужно функции на первом и втором графике для каждой из машин.
Разные машины приведены в общем-то для расширения кругозора (все равно они в стойках стоят и на праздниках бездельничают)
В любом случае — сравнение не в пользу АМД — серверный процессор от Интела тоже участвовал :)
0
Еще бы через CUDA прогнать
+2
UFO just landed and posted this here
Темой моей курсовой работы было «Реализация многопоточности в .Net». Хочу выложить на хабр, но не хватает кармы…
+1
------простые числа на питоне-------------- #!/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
рад и удивлен))
0
Ну, несколько секунд для простых чисел до 10к — это как-то не очень быстро…
0
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
А так? :)
0
«Очень» оптимальная программа — много лишних итераций как в главном цикле, так и в функции.
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) )
0
Интересно было бы на Erlang посмотреть в такой же ситуации :) Не займетесь?
0
В данном случае выигрыша не будет. Скорее всего, Erlang будет медленнее из-за динамической типизации.
+1
А вот не скажите. Все зависит от реализации. К тому же «динамический язык» не значит «медленный язык». Скажем, меня жутко удивило, что Dolphin Smalltalk считал некоторые тесты (кажется простые числа там тоже были) сопоставимо а то и быстрее альтернатив.
Хотя сами разработчики Dolphin-а говорят (и я с ними согласен) что целочисленные тесты для таких дел это зло и не могут являться критерием скорости языка. В том смысле, что реальные данные появляются в реальных же, боевых задачах, где автоматическая оптимизация кода скажет свое слово.
Хотя сами разработчики Dolphin-а говорят (и я с ними согласен) что целочисленные тесты для таких дел это зло и не могут являться критерием скорости языка. В том смысле, что реальные данные появляются в реальных же, боевых задачах, где автоматическая оптимизация кода скажет свое слово.
-1
На той же википедии (на заметку)
За нахождение простого числа из более чем 108 десятичных цифр EFF назначила награду в 150000 долларов США.
0
Код в студию!
+1
Код не выложили, Parallel Extensions навряд ли юзали, так что ядро вы использовали скорее всего одно. Хотелось бы видеть также результаты после использования NGen'а. Конфигурации серверов не указаны(интересует конкретные процессоры и оперативная память). На другие косяки вам тоже указали. В общем очень скользкий тест, который стоит провести более честно;)
+1
Sign up to leave a comment.
Параллельные вычисления при поиске простых чисел.