Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 24 25 26 27 28 29 30 [31] 32 33   вперед  Ctrl
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
vino
студентик, IsFactor64(6,2) = false, IsFactor64(7,2) = true
Что не так?


Данный алгоритм пригоден для проверки нечетных чисел(все простые) на нечетные делители(либо простые, либо предполагаемые простые). В остальных случаях он может работать некорректно.
10 май 09, 15:17    [7165549]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
Данный случай тривиален . Если возникла необходимость проверить через эту функцию делимость двух четных чисел, то делим обоюдно делитель и делимое на 2, до тех пор пока делитель не станет нечетным, далее используем нашу функцию, вслучае если делитель четный, а делимое нечетное то делитель никогда не будет составным множителем для делимого , те
к мод р никогда неравно 0, где к - нечентое р - четное
10 май 09, 15:26    [7165553]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 40512
Результат работы PBFA для 64х битного алгоритма. Общее время работы - около 4 часов. Результат - совпадает с 32х битным. С учётом исправленной ошибки, чисел стало на 1 больше, и магическое число Мерсена попало наконец-то в конец списка.

#Pi
12
23
35
47
511
613
717
819
923
1029
1131
....
1050975622147483579
1050975632147483587
1050975642147483629
1050975652147483647


С тестами 32-х бит я закончил. Больше они мне неинтересны. Буду форсировать длинную разрядную сетку. Совершенно необходима оптимизация.

Для начала попробую пересобрать исходник под другой платформой (Linux-Suse64, gcc). Посмотрю, как там.
10 май 09, 16:59    [7165598]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
mayton
Результат работы PBFA для 64х битного алгоритма. Общее время работы - около 4 часов. Результат - совпадает с 32х битным. С учётом исправленной ошибки, чисел стало на 1 больше, и магическое число Мерсена попало наконец-то в конец списка.

#Pi
12
23
35
47
511
613
717
819
923
1029
1131
....
1050975622147483579
1050975632147483587
1050975642147483629
1050975652147483647


С тестами 32-х бит я закончил. Больше они мне неинтересны. Буду форсировать длинную разрядную сетку. Совершенно необходима оптимизация.

Для начала попробую пересобрать исходник под другой платформой (Linux-Suse64, gcc). Посмотрю, как там.

А каким компилятором под Win32 вы пользовались?
10 май 09, 22:22    [7165971]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 40512
VS 2005 Exp.
10 май 09, 22:28    [7165994]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
mayton
VS 2005 Exp.

Сравнивал помню одинаковый код сортировки на 2008 студии и 6... был удивлен результатом-код, сгенерированный 6 отработал побыстрее.
10 май 09, 23:11    [7166077]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
Переделал фунцию проверки на множитель под ассемблер...
+ ассемблерный вариант
function IsFactor64asm(value, divisor: Int64): Boolean;

asm
    push ECX
    push EBX
    push ESI
    push EDI
    mov EDX, [EBP + $14] // EDX:EAX = value
    mov EAX, [EBP + $10]
    mov EBX, [EBP + $0c] // EBX:ECX = divisor
    mov ECX, [EBP + $08]
    mov ESI, ECX         // EDI:ESI = 2*divisor
    mov EDI, EBX
    shld EDI, ESI, $01
    shl ESI, 1
    jmp @@1
@@5:test AL, $01
    jz @@6
    sub EAX, ECX
    sbb EDX, EBX
    shrd EAX, EDX, $01
    shr EDX, 1
    jmp @@1
@@6:shrd EAX, EDX, $01
    shr EDX, 1
@@1:cmp  EDI, EDX
    jnz  @@2
    cmp  ESI, EAX 
    jbe  @@5
@@3: jmp  @@4
@@2: db $7E, $DE  //jle @@3
@@4: cmp EDX, EBX
    jnz @@7
    cmp EAX, ECX
@@7:setz AL
    pop EDI
    pop ESI
    pop EBX
    pop ECX
end;

Что могу сказать... Грустно... Быстродействие хоть и выросло, но решение проблемы таким способом неинтерсно, а идеи по алгоритмической части никак не приходят в голову.
10 май 09, 23:14    [7166085]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
vino
Member

Откуда:
Сообщений: 1191
студентик
Переделал фунцию проверки на множитель под ассемблер...
+
+ ассемблерный вариант
function IsFactor64asm(value, divisor: Int64): Boolean;

asm
    push ECX
    push EBX
    push ESI
    push EDI
    mov EDX, [EBP + $14] // EDX:EAX = value
    mov EAX, [EBP + $10]
    mov EBX, [EBP + $0c] // EBX:ECX = divisor
    mov ECX, [EBP + $08]
    mov ESI, ECX         // EDI:ESI = 2*divisor
    mov EDI, EBX
    shld EDI, ESI, $01
    shl ESI, 1
    jmp @@1
@@5:test AL, $01
    jz @@6
    sub EAX, ECX
    sbb EDX, EBX
    shrd EAX, EDX, $01
    shr EDX, 1
    jmp @@1
@@6:shrd EAX, EDX, $01
    shr EDX, 1
@@1:cmp  EDI, EDX
    jnz  @@2
    cmp  ESI, EAX 
    jbe  @@5
@@3: jmp  @@4
@@2: db $7E, $DE  //jle @@3
@@4: cmp EDX, EBX
    jnz @@7
    cmp EAX, ECX
@@7:setz AL
    pop EDI
    pop ESI
    pop EBX
    pop ECX
end;

Что могу сказать... Грустно...

Как минимум, можно выбросить еще +
+ повторы
function IsFactor64asm(value, divisor: Int64): Boolean;

asm
    push ECX
    push EBX
    push ESI
    push EDI
    mov EDX, [EBP + $14] // EDX:EAX = value
    mov EAX, [EBP + $10]
    mov EBX, [EBP + $0c] // EBX:ECX = divisor
    mov ECX, [EBP + $08]
    mov ESI, ECX         // EDI:ESI = 2*divisor
    mov EDI, EBX
    shld EDI, ESI, $01
    shl ESI, 1
    jmp @@1
@@5:test AL, $01
    jz @@6
    sub EAX, ECX
    sbb EDX, EBX
@@6:shrd EAX, EDX, $01
    shr EDX, 1
@@1:cmp  EDI, EDX
    jnz  @@2
    cmp  ESI, EAX 
    jbe  @@5
@@3: jmp  @@4
@@2: db $7E, $DE  //jle @@3 ???
@@4: cmp EDX, EBX
    jnz @@7
    cmp EAX, ECX
@@7:setz AL
    pop EDI
    pop ESI
    pop EBX
    pop ECX
end;
11 май 09, 13:36    [7166702]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
vino
Member

Откуда:
Сообщений: 1191
+ Вспоминая молодость
function IsFactor64asm(value, divisor: Int64): Boolean;
function IsFactor64asm(value, divisor: Int64): Boolean;
asm
    push  ECX
    push  EBX
    push  ESI
    push  EDI

    mov   EBX, [EBP + $0c] // EBX:ECX = divisor
    mov   ECX, [EBP + $08]
    mov   EDX, [EBP + $14] // EDX:EAX = value
    mov   EAX, [EBP + $10]
    mov   ESI, ECX         // EDI:ESI = 2*divisor
    mov   EDI, EBX
    shl   ESI, 1
    shld  EDI, ECX, $01
    jmp   @@1
@@5:
    test  AL, $01            // ?: odd(value) 
    jz    @@6                // if not
    sub   EAX, ECX         // value-divisor
    sbb   EDX, EBX
@@6:
    shrd  EAX, EDX, $01  // div 2
    shr   EDX, 1
@@1:                         // while:
    cmp   EDI, EDX         // ?: 2divisor # value
    ja    @@4                // if > then break
    jb    @@5                // if < then continue
    cmp   ESI, EAX         
    jb    @@5 
    je    @@7                // if = then result := true
@@4:                         // Result:
    cmp  EDX, EBX         // ?: divisor # value
    jne   @@7               // if <> then result := false 
    cmp   EAX, ECX
@@7:
    setz  AL

    pop   EDI
    pop   ESI
    pop   EBX
    pop   ECX
end;
11 май 09, 15:22    [7166890]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
vino
студентик
Переделал фунцию проверки на множитель под ассемблер...
++
+ ассемблерный вариант
function IsFactor64asm(value, divisor: Int64): Boolean;

asm
    push ECX
    push EBX
    push ESI
    push EDI
    mov EDX, [EBP + $14] // EDX:EAX = value
    mov EAX, [EBP + $10]
    mov EBX, [EBP + $0c] // EBX:ECX = divisor
    mov ECX, [EBP + $08]
    mov ESI, ECX         // EDI:ESI = 2*divisor
    mov EDI, EBX
    shld EDI, ESI, $01
    shl ESI, 1
    jmp @@1
@@5:test AL, $01
    jz @@6
    sub EAX, ECX
    sbb EDX, EBX
    shrd EAX, EDX, $01
    shr EDX, 1
    jmp @@1
@@6:shrd EAX, EDX, $01
    shr EDX, 1
@@1:cmp  EDI, EDX
    jnz  @@2
    cmp  ESI, EAX 
    jbe  @@5
@@3: jmp  @@4
@@2: db $7E, $DE  //jle @@3
@@4: cmp EDX, EBX
    jnz @@7
    cmp EAX, ECX
@@7:setz AL
    pop EDI
    pop ESI
    pop EBX
    pop ECX
end;

Что могу сказать... Грустно...

Как минимум, можно выбросить еще ++
+ повторы
function IsFactor64asm(value, divisor: Int64): Boolean;

asm
    push ECX
    push EBX
    push ESI
    push EDI
    mov EDX, [EBP + $14] // EDX:EAX = value
    mov EAX, [EBP + $10]
    mov EBX, [EBP + $0c] // EBX:ECX = divisor
    mov ECX, [EBP + $08]
    mov ESI, ECX         // EDI:ESI = 2*divisor
    mov EDI, EBX
    shld EDI, ESI, $01
    shl ESI, 1
    jmp @@1
@@5:test AL, $01
    jz @@6
    sub EAX, ECX
    sbb EDX, EBX
@@6:shrd EAX, EDX, $01
    shr EDX, 1
@@1:cmp  EDI, EDX
    jnz  @@2
    cmp  ESI, EAX 
    jbe  @@5
@@3: jmp  @@4
@@2: db $7E, $DE  //jle @@3 ???
@@4: cmp EDX, EBX
    jnz @@7
    cmp EAX, ECX
@@7:setz AL
    pop EDI
    pop ESI
    pop EBX
    pop ECX
end;
11 май 09, 17:13    [7167075]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
небольшое пояснение по поводу @@2: db $7E, $DE . В ходе написания этого фрагмента столкнулся с проблемой компилятор дельфи активно отказывался компилировать эту инструкцию, все дело видимо в проходах компилятора, так как тут запутанная логика о компилятор не успевает отследить данный переход поэтому и выкидывает его из кода.
11 май 09, 17:14    [7167077]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
vino
Member

Откуда:
Сообщений: 1191
студентик, последний мой вариант компилится в Delphi
11 май 09, 18:09    [7167154]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9372
студентик
все дело видимо в проходах компилятора, так как тут запутанная логика о компилятор не успевает отследить данный переход поэтому и выкидывает его из кода.


это козырное объяснение
11 май 09, 18:17    [7167170]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
vino
студентик, последний мой вариант компилится в Delphi

Уже проверил:) Кстати мой тоже просто нужен пересчет смещения всякий раз когда будет изменен ко до перехода.
11 май 09, 18:34    [7167203]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
Gluk (Kazan)
студентик
все дело видимо в проходах компилятора, так как тут запутанная логика о компилятор не успевает отследить данный переход поэтому и выкидывает его из кода.


это козырное объяснение

И не говорите...:) Хотя можно и короче компилирование встроенного асма, по-видимому, однопроходное
11 май 09, 18:36    [7167206]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 40512
Я выкурил следующий документ касаемый С++. Называется Porting Applications to 64bit от Intel.

Вот такая там есть табличка.

К сообщению приложен файл. Размер - 0Kb
11 май 09, 22:18    [7167475]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 40512
Щас посмотрим на моей винде.

Compiller options:
-----------------
_M_IA64                        : [ ]
Optimize for processor         : Intel Pentium Pro, Pentium II, Pentium III, and Pentium 4 processors (/G6)
Compilled for CPU architecture : SSE-2 ( /arch:SSE2)
Version                        : 14.00
Unicode support                : [x] (_UNICODE)
Long Integer size(bits)        : 32
Conformance with the ANSI C    : NO
_WIN32                         : [x]
_WIN64                         : [ ]
__LP64_                        : [ ]
unix                           : [ ]
Multithreading support         : [x] (_MT)
11 май 09, 22:27    [7167484]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 40512
Да. Так я и думал.

Вот тот-же фрагмент репорта, собраный под OpenSuse Linux-x86_64 в GCC
mayton@alleria:~/cpp/pbfa/debug/src> ./pbfa

Overall report :
==================

Compiller options:
-----------------
_M_IA64                        : [ ]
Optimize for processor         : Unknown
Compilled for CPU architecture : Unknown
Version                        : Unknown
Unicode support                : [ ]
Long Integer size(bits)        : 64
Conformance with the ANSI C    : YES
_WIN32                         : [ ]
_WIN64                         : [ ]
__LP64_                        : [ ]
unix                           : [x]
Multithreading support         : [ ]

12 май 09, 00:02    [7167668]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
mayton
Да. Так я и думал.

Вот тот-же фрагмент репорта, собраный под OpenSuse Linux-x86_64 в GCC
mayton@alleria:~/cpp/pbfa/debug/src> ./pbfa

Overall report :
==================

Compiller options:
-----------------
_M_IA64                        : [ ]
Optimize for processor         : Unknown
Compilled for CPU architecture : Unknown
Version                        : Unknown
Unicode support                : [ ]
Long Integer size(bits)        : 64
Conformance with the ANSI C    : YES
_WIN32                         : [ ]
_WIN64                         : [ ]
__LP64_                        : [ ]
unix                           : [x]
Multithreading support         : [ ]


Что-нибудь нашли?
12 май 09, 01:37    [7167776]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 40512
Разрядность long integer-a.
12 май 09, 10:11    [7168279]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 40512
Пришли новые цифры. На той-же рабочей станции под OpenSuse Linux я, используя KDevelop пересобрал проект и запустил сбор чисел для диапазона 2^31. Процесс занял около 3,5 часов. Это немного лучше чем на Windows, но хуже чем я прогнозировал..

Из трёх профилей сборки (Debug, Default и Optimized) я выбрал Optimized, хотя особой разницы между ними пока не обнаружил.

Overall report :
==================

Compiller options:
-----------------
Unicode support                : [ ]
Long Integer size(bits)        : 64
Conformance with the ANSI C    : YES
unix                           : [x]
 Unix Compiller Specific Options
 -------------------------------


PBFA algorithm:
-----------------
Continue mode                  : [ ]
Primes factorisation function  : Standard %
Primes staging engine          : Differencial
Main computing mode            : 64 bit
Range                          : [2..2147483647]
Primes detected                : 105097565
Max prime found                : 2147483647
Twins detected                 : 6810672
Mersenn detected               : 8
Max Mersenn detected           : 2147483647
Normal memory cache used       : 0 K
Debug mode                     : [ ]
Differencial 8-bit cache used  : 131072 K (105097564 elements,sizeof(UINT8)=1)
Differencial 16-bit cache used : 0 K (0 elements, sizeof(UINT16)=2)
Differencial 32-bit cache used : 0 K (0 elements, sizeof(UINT32)=4)
Differencial 64-bit cache used : 0 K (0elements,sizeof(UINT64)=8)
AVG speed generation           : 8098 units/sec
Primes/overall ratio           : 0.04893987
Elapsed time                   : 12977 sec

Прошу прощения за внешний вид отчёта. Я постоянно его изменяю, пытаясь получить больше полезной информации в текущем компилляторе, но сохраняя преемсвтенность двух платформ. Поэтому он может слегка отличаться от виндозного. Но главные счётчики, такие как время и количество чисел, остаются неизменно на месте.

Кстати. Никто сходу не помнит, какую опцию надо указать в makefile чтобы получить ассемблерный листинг?
12 май 09, 17:50    [7171384]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
clihlt
Member

Откуда: Донецк
Сообщений: 1122
mayton,

Для gcc -S
12 май 09, 18:00    [7171440]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 40512
Покорректировал Makefile

Нашёл строчку
...
AWK = gawk
CC = gcc
CCDEPMODE = depmode=gcc3
CFLAGS = -g -O2
CPP = gcc -E 
CPPFLAGS = 
CXX = g++
CXXCPP = g++ -E
CXXDEPMODE = depmode=gcc3
CXXFLAGS = -O2 -g0
CYGPATH_W = echo
DEFS = -DHAVE_CONFIG_H
..

Заменил на

CPP = gcc -E -S

Ничего не вышло
12 май 09, 18:19    [7171537]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
clihlt
Member

Откуда: Донецк
Сообщений: 1122
mayton,

надо убрать ключик -E. Он с ним только препроцессит.
у меня
gcc -S test.c
пашет. Генерит файл test.s
12 май 09, 19:11    [7171744]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
clihlt
Member

Откуда: Донецк
Сообщений: 1122
clihlt,

и как вариант доваить ключ еще сюда
CFLAGS = -g -O2 -S
12 май 09, 19:13    [7171748]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 24 25 26 27 28 29 30 [31] 32 33   вперед  Ctrl
Все форумы / Программирование Ответить