Автор |
Сообщение |
|
|
Заголовок сообщения: |
|
|
|
forther писал(а): да, закрыта. спасибо за ссылку! для тех, кто поленился посмотреть в конец:
Код: : q3 ( n -- q ) 3 - dup 2 + over 2* 3 + over 2 + * * 24 / ; Ага, сделано уже (с) У вас ошибка, правильно так: Код: : q3 ( n -- q ) 4 - DUP 2 + SWAP 2* 3 + OVER 2 + * * 24 / ; можно проще Код: : Q3 DUP 2- DUP 2* 1- * * 24 / ; forther писал(а): Имеет смысл считать двойной результат: Код: : q3 ( n -- d ) 3 - dup 2 + over 2* 3 + over 2 + m* rot 24 m*/ ; В СПФ нет функции UD/ ( ud un --> ud ), определим на ассме: Код: : UD/ ( ud un --> ud ) D^D S=A A=@P $ 4 Pa /S B=A A=@P /S @P=A A=B ;
: QQ3 ( n -- dq ) DUP 2- DUP 2* 1- * M* 24 UD/ ; 20000 QQ3 D. ЛОГ Код: 666516675000 Ok
[quote="forther"]да, закрыта. спасибо за ссылку! для тех, кто поленился посмотреть в конец:
Код: : q3 ( n -- q ) 3 - dup 2 + over 2* 3 + over 2 + * * 24 / ;[/quote] Ага, [b]сделано уже (с)[/b]
У вас ошибка, правильно так: [code]: q3 ( n -- q ) 4 - DUP 2 + SWAP 2* 3 + OVER 2 + * * 24 / ;[/code] можно проще [code]: Q3 DUP 2- DUP 2* 1- * * 24 / ;[/code] [quote="forther"]Имеет смысл считать двойной результат: Код: : q3 ( n -- d ) 3 - dup 2 + over 2* 3 + over 2 + m* rot 24 m*/ ;[/quote]
В СПФ нет функции UD/ ( ud un --> ud ), определим на ассме:
[code]: UD/ ( ud un --> ud ) D^D S=A A=@P $ 4 Pa /S B=A A=@P /S @P=A A=B ;
: QQ3 ( n -- dq ) DUP 2- DUP 2* 1- * M* 24 UD/ ; 20000 QQ3 D.[/code]
ЛОГ[code] 666516675000 Ok[/code]
|
|
|
|
Добавлено: Вт янв 26, 2010 13:14 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
Кстати, chess, при N=5000 результат 34 битный, так что ваши сравнения на таких N могут не совсем корректно сравнивать. Если, конечно, у вас не 64 битный форт. Имеет смысл считать двойной результат:
Код: : q3 ( n -- d ) 3 - dup 2 + over 2* 3 + over 2 + m* rot 24 m*/ ;
Кстати, chess, при N=5000 результат 34 битный, так что ваши сравнения на таких N могут не совсем корректно сравнивать. Если, конечно, у вас не 64 битный форт. Имеет смысл считать двойной результат:
[code]: q3 ( n -- d ) 3 - dup 2 + over 2* 3 + over 2 + m* rot 24 m*/ ;[/code]
|
|
|
|
Добавлено: Вт янв 26, 2010 00:30 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
без определения solution-table[] это не решение. незачот.
без определения solution-table[] это не решение. незачот.
|
|
|
|
Добавлено: Пн янв 25, 2010 23:52 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
Да еще проще.
Код: : q3 ( n -- q ) CELLS solution-table[] + @ ;
Да еще проще.
[code]: q3 ( n -- q ) CELLS solution-table[] + @ ;[/code]
|
|
|
|
Добавлено: Пн янв 25, 2010 23:35 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
да, закрыта. спасибо за ссылку! для тех, кто поленился посмотреть в конец:
Код: : q3 ( n -- q ) 3 - dup 2 + over 2* 3 + over 2 + * * 24 / ;
оптимизация ...
да, закрыта. спасибо за ссылку! для тех, кто поленился посмотреть в конец:
[code]: q3 ( n -- q ) 3 - dup 2 + over 2* 3 + over 2 + * * 24 / ;[/code]
оптимизация ...
|
|
|
|
Добавлено: Пн янв 25, 2010 23:05 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
WingLion писал(а): garbler писал(а): требование одно единственное: А+Б > В ой ли? ...skip... Возьмите числа 1,2,100 и попробуйте треугольник с такими длинами построить. В евклидовом пространстве это явно не получится. А неевклидово пространство - не от этой задачи
разумеется имелась ввиду отсортированная последовательность (т.е. условие автоматически накладывается на все стороны).
и вообще: http://www.research.att.com/~njas/sequences/A002623 - number of nondegenerate triangles that can be made from rods of length 1,2,3,4,...,n ..... и куча других формулировок. все формулы в конце.
тема закрыта?
[quote="WingLion"][quote="garbler"]требование одно единственное: А+Б > В [/quote] ой ли? ...skip... Возьмите числа 1,2,100 и попробуйте треугольник с такими длинами построить. В евклидовом пространстве это явно не получится. А неевклидово пространство - не от этой задачи[/quote]
разумеется имелась ввиду отсортированная последовательность (т.е. условие автоматически накладывается на все стороны).
и вообще: http://www.research.att.com/~njas/sequences/A002623 - number of nondegenerate triangles that can be made from rods of length 1,2,3,4,...,n ..... и куча других формулировок. все формулы в конце.
тема закрыта?
|
|
|
|
Добавлено: Пн янв 25, 2010 15:34 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
Чуть изменил код на форте, для переписывания на встроенном асс-ме:
Код: : Q3 ( N -- Q ) 0 OVER 2/ 1 SWAP DO OVER I 2* - DUP 1- * 2/ + -1 +LOOP NIP ;
SEE Q3
\ код на ассме : Q3a ( N -- Q ) S^S ( сумма ) B=A ( N ) C=A 1C>> ( I ) L1: D=B A=C 1A<< D-A A=D A-- *D 1A>> S+A C-- L1 J0<> A=S ;
SEE Q3a
: pr-fvm 5000 Q3 ; METER pr-fvm
: pr-trg 5000 Q3a ; METER pr-trg лог Код: CODE Q3 5AEB13 8945FC MOV FC [EBP] , EAX 5AEB16 C745F800000000 MOV F8 [EBP] , # 0 5AEB1D D1F8 SAR EAX , 1 5AEB1F C745F401000000 MOV F4 [EBP] , # 1 5AEB26 BA00000080 MOV EDX , # 80000000 5AEB2B 2B55F4 SUB EDX , F4 [EBP] 5AEB2E 8D1C02 LEA EBX , [EDX] [EAX] 5AEB31 8B45F8 MOV EAX , F8 [EBP] 5AEB34 8D6DFC LEA EBP , FC [EBP] 5AEB37 6877EB5A00 PUSH , # 5AEB77 5AEB3C 52 PUSH EDX 5AEB3D 53 PUSH EBX 5AEB3E 90 XCHG EAX, EAX 5AEB3F 90 XCHG EAX, EAX 5AEB40 8945FC MOV FC [EBP] , EAX 5AEB43 8B4500 MOV EAX , 0 [EBP] 5AEB46 8945F8 MOV F8 [EBP] , EAX 5AEB49 8B0424 MOV EAX , [ESP] 5AEB4C 2B442404 SUB EAX , 4 [ESP] 5AEB50 8D044500000000 LEA EAX , 0 [EAX*2] 5AEB57 F7D8 NEG EAX 5AEB59 0345F8 ADD EAX , F8 [EBP] 5AEB5C 8945F8 MOV F8 [EBP] , EAX 5AEB5F 8D40FF LEA EAX , FF [EAX] 5AEB62 F76DF8 IMUL F8 [EBP] 5AEB65 D1F8 SAR EAX , 1 5AEB67 0345FC ADD EAX , FC [EBP] 5AEB6A 810424FFFFFFFF ADD [ESP] , # FFFFFFFF 5AEB71 71CD JNO 5AEB40 5AEB73 8D64240C LEA ESP , C [ESP] 5AEB77 8D6D04 LEA EBP , 4 [EBP] 5AEB7A C3 RET NEAR END-CODE ( 104 bytes, 32 instructions )
CODE Q3a 5AEB8B 33F6 XOR ESI , ESI 5AEB8D 8BD8 MOV EBX , EAX 5AEB8F 8BC8 MOV ECX , EAX 5AEB91 D1E9 SHR ECX , 1 5AEB93 8BD3 MOV EDX , EBX 5AEB95 8BC1 MOV EAX , ECX 5AEB97 D1E0 SHL EAX , 1 5AEB99 2BD0 SUB EDX , EAX 5AEB9B 8BC2 MOV EAX , EDX 5AEB9D 48 DEC EAX 5AEB9E F7EA IMUL EDX 5AEBA0 D1E8 SHR EAX , 1 5AEBA2 03F0 ADD ESI , EAX 5AEBA4 49 DEC ECX 5AEBA5 75EC JNE 5AEB93 5AEBA7 8BC6 MOV EAX , ESI 5AEBA9 C3 RET NEAR END-CODE ( 31 bytes, 17 instructions )
26829 26667 ( при Ft=3ГГц t=8,6 мкс) 14229 14157 ( при Ft=3ГГц t=4,6 мкс) Ok
ps.
1. Рациональная организация входных данных может резко упростить алгоритм решения и его кодирование.
( если бы числа нат. ряда были расположены в случайном порядке, то сложность была бы значительно выше ).
Поэтому есть смысл в анализе необходимости этапа подготовки исх. данных.
2. Алгоритм настолько прост, что можно было убрать все аспекты эмуляции
виртуальной машины форта, в том числе и стек данных, то есть
привести код к виду оптимальному для данной целевой машины(вручную конечно).
(нет переписывания кэш-памяти данных и кода по ходу исполнения - приоритет 1,
все вычисления только в регистрах - приоритет 2)
В результате сравнения видно, что ускорение "родного" кода по сравнению с peephole-оптимизированным
кодом спф4 всего-то в два раза. Куски peephole-оптимизированного кода сращиваются друг с другом
через стек данных. Собственно это обстоятельство и приводит к замедлению кода в два раза.
Чуть изменил код на форте, для переписывания на встроенном асс-ме:
[code]: Q3 ( N -- Q ) 0 OVER 2/ 1 SWAP DO OVER I 2* - DUP 1- * 2/ + -1 +LOOP NIP ;
SEE Q3
\ код на ассме : Q3a ( N -- Q ) S^S ( сумма ) B=A ( N ) C=A 1C>> ( I ) L1: D=B A=C 1A<< D-A A=D A-- *D 1A>> S+A C-- L1 J0<> A=S ;
SEE Q3a
: pr-fvm 5000 Q3 ; METER pr-fvm
: pr-trg 5000 Q3a ; METER pr-trg[/code] лог [code]CODE Q3 5AEB13 8945FC MOV FC [EBP] , EAX 5AEB16 C745F800000000 MOV F8 [EBP] , # 0 5AEB1D D1F8 SAR EAX , 1 5AEB1F C745F401000000 MOV F4 [EBP] , # 1 5AEB26 BA00000080 MOV EDX , # 80000000 5AEB2B 2B55F4 SUB EDX , F4 [EBP] 5AEB2E 8D1C02 LEA EBX , [EDX] [EAX] 5AEB31 8B45F8 MOV EAX , F8 [EBP] 5AEB34 8D6DFC LEA EBP , FC [EBP] 5AEB37 6877EB5A00 PUSH , # 5AEB77 5AEB3C 52 PUSH EDX 5AEB3D 53 PUSH EBX 5AEB3E 90 XCHG EAX, EAX 5AEB3F 90 XCHG EAX, EAX 5AEB40 8945FC MOV FC [EBP] , EAX 5AEB43 8B4500 MOV EAX , 0 [EBP] 5AEB46 8945F8 MOV F8 [EBP] , EAX 5AEB49 8B0424 MOV EAX , [ESP] 5AEB4C 2B442404 SUB EAX , 4 [ESP] 5AEB50 8D044500000000 LEA EAX , 0 [EAX*2] 5AEB57 F7D8 NEG EAX 5AEB59 0345F8 ADD EAX , F8 [EBP] 5AEB5C 8945F8 MOV F8 [EBP] , EAX 5AEB5F 8D40FF LEA EAX , FF [EAX] 5AEB62 F76DF8 IMUL F8 [EBP] 5AEB65 D1F8 SAR EAX , 1 5AEB67 0345FC ADD EAX , FC [EBP] 5AEB6A 810424FFFFFFFF ADD [ESP] , # FFFFFFFF 5AEB71 71CD JNO 5AEB40 5AEB73 8D64240C LEA ESP , C [ESP] 5AEB77 8D6D04 LEA EBP , 4 [EBP] 5AEB7A C3 RET NEAR END-CODE ( 104 bytes, 32 instructions )
CODE Q3a 5AEB8B 33F6 XOR ESI , ESI 5AEB8D 8BD8 MOV EBX , EAX 5AEB8F 8BC8 MOV ECX , EAX 5AEB91 D1E9 SHR ECX , 1 5AEB93 8BD3 MOV EDX , EBX 5AEB95 8BC1 MOV EAX , ECX 5AEB97 D1E0 SHL EAX , 1 5AEB99 2BD0 SUB EDX , EAX 5AEB9B 8BC2 MOV EAX , EDX 5AEB9D 48 DEC EAX 5AEB9E F7EA IMUL EDX 5AEBA0 D1E8 SHR EAX , 1 5AEBA2 03F0 ADD ESI , EAX 5AEBA4 49 DEC ECX 5AEBA5 75EC JNE 5AEB93 5AEBA7 8BC6 MOV EAX , ESI 5AEBA9 C3 RET NEAR END-CODE ( 31 bytes, 17 instructions )
26829 26667 ( при Ft=3ГГц t=8,6 мкс) 14229 14157 ( при Ft=3ГГц t=4,6 мкс) Ok[/code]
ps.
1. Рациональная организация входных данных может резко упростить алгоритм решения и его кодирование.
( если бы числа нат. ряда были расположены в случайном порядке, то сложность была бы значительно выше ).
Поэтому есть смысл в анализе необходимости этапа подготовки исх. данных.
2. Алгоритм настолько прост, что можно было убрать все аспекты эмуляции
виртуальной машины форта, в том числе и стек данных, то есть
привести код к виду оптимальному для данной целевой машины(вручную конечно).
(нет переписывания кэш-памяти данных и кода по ходу исполнения - приоритет 1,
все вычисления только в регистрах - приоритет 2)
В результате сравнения видно, что ускорение "родного" кода по сравнению с peephole-оптимизированным
кодом спф4 всего-то в два раза. Куски peephole-оптимизированного кода сращиваются друг с другом
через стек данных. Собственно это обстоятельство и приводит к замедлению кода в два раза.
|
|
|
|
Добавлено: Пн янв 25, 2010 12:57 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
можно еще проще:
Код: : Q3 ( N -- Q ) 0 OVER 2/ 1+ 1 DO OVER I 2* - DUP 1- * 2/ + LOOP NIP ;
можно еще проще:
[code]: Q3 ( N -- Q ) 0 OVER 2/ 1+ 1 DO OVER I 2* - DUP 1- * 2/ + LOOP NIP ;[/code]
|
|
|
|
Добавлено: Сб янв 23, 2010 23:56 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
<pre>
\ количество троек различных треугольников # с одной фиксированной вершиной u
: nnn ( u --> # )
0 >R
3 - BEGIN DUP 0 > WHILE
DUP R+
2 -
REPEAT DROP R> ;
\ общее количество = сумме ряда кол-во треугольников для u-1 + количество треугольников для u
: xxx ( u --> # )
0 >R
3 BEGIN DDUP - WHILE
DUP nnn R+
1 +
REPEAT DDROP R> ;
\
: triangles ( u --> ) BEGIN DUP xxx . CR 1 - DUP 3 = UNTIL DROP ;
\ поэтому, собственно можно не считать в цикле каждый раз
\ как сделано выше, а использовать накопительную переменную
: tr ( u --> )
3 0 >R BEGIN DDUP - WHILE
DUP nnn R+
R@ . CR
1 +
REPEAT DDROP RDROP ;
</pre>
log:
<pre>
FORTH(0)> 33 triangles
2360
2135
1925
1729
1547
1378
1222
1078
946
825
715
615
525
444
372
308
252
203
161
125
95
70
50
34
22
13
7
3
1
0
</pre>
принцип тот же, что и в решении с неправильно понятым ТЗ.
<pre>
\ количество троек различных треугольников # с одной фиксированной вершиной u
: nnn ( u --> # )
0 >R
3 - BEGIN DUP 0 > WHILE
DUP R+
2 -
REPEAT DROP R> ;
\ общее количество = сумме ряда кол-во треугольников для u-1 + количество треугольников для u
: xxx ( u --> # )
0 >R
3 BEGIN DDUP - WHILE
DUP nnn R+
1 +
REPEAT DDROP R> ;
\
: triangles ( u --> ) BEGIN DUP xxx . CR 1 - DUP 3 = UNTIL DROP ;
\ поэтому, собственно можно не считать в цикле каждый раз
\ как сделано выше, а использовать накопительную переменную
: tr ( u --> )
3 0 >R BEGIN DDUP - WHILE
DUP nnn R+
R@ . CR
1 +
REPEAT DDROP RDROP ;
</pre>
log:
<pre>
FORTH(0)> 33 triangles
2360
2135
1925
1729
1547
1378
1222
1078
946
825
715
615
525
444
372
308
252
203
161
125
95
70
50
34
22
13
7
3
1
0
</pre>
принцип тот же, что и в решении с неправильно понятым ТЗ.
|
|
|
|
Добавлено: Сб янв 23, 2010 11:13 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
mOleg писал(а): таким образом считать ничего не надо особо.
Условие задачи вами не понято.
Вот пример: N=6
1 2 3 4 5 6
треугольные тройки:
(234) (245) (256) (345) (346) (356) (456)
Q3=7
Ни в одной тройке нет одинаковых чисел.
[quote="mOleg"]таким образом считать ничего не надо особо.[/quote]
Условие задачи вами не понято.
Вот пример: N=6
1 2 3 4 5 6
треугольные тройки:
(234) (245) (256) (345) (346) (356) (456)
Q3=7
Ни в одной тройке нет одинаковых чисел.
|
|
|
|
Добавлено: Сб янв 23, 2010 10:21 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
таким образом считать ничего не надо особо.
<pre>
: Count ( u --> # )
0 >R
BEGIN DUP 0 > WHILE
DUP R+
2 -
REPEAT DROP
R> ;
\ и подсчет ряда:
: triangles ( u --> )
BEGIN DUP WHILE
DUP Count . CR
1 -
REPEAT DROP ;
</pre>
лог:
<pre>
FORTH(0)>20 triangles
110
100
90
81
72
64
56
49
42
36
30
25
20
16
12
9
6
4
2
1
</pre>
таким образом считать ничего не надо особо.
<pre>
: Count ( u --> # )
0 >R
BEGIN DUP 0 > WHILE
DUP R+
2 -
REPEAT DROP
R> ;
\ и подсчет ряда:
: triangles ( u --> )
BEGIN DUP WHILE
DUP Count . CR
1 -
REPEAT DROP ;
</pre>
лог:
<pre>
FORTH(0)>20 triangles
110
100
90
81
72
64
56
49
42
36
30
25
20
16
12
9
6
4
2
1
</pre>
|
|
|
|
Добавлено: Сб янв 23, 2010 09:51 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
мндя, у мя получаются другие числа.
Для того, чтобы получился треугольник, нужно, чтобы сумма двух других сторон была больше на 1 самой длинной.
то есть, для длины в 1, возможен только один равносторонний треугольник с длинами 1+1
<pre>
для 2: 2+2;2+1 = 2 варианта
для 3: 3+3;3+2;3+1
2+2 = 4 варианта
для 4: 4+4;4+3;4+2;4+1
3+3;3+2 = 6 вариантов
для 5: 5+5;5+4;5+3;5+2;5+1
4+4;4+3;4+2
3+3 = 9 вариантов
12
16
20
25
и так далее.
</pre>
мндя, у мя получаются другие числа.
Для того, чтобы получился треугольник, нужно, чтобы сумма двух других сторон была больше на 1 самой длинной.
то есть, для длины в 1, возможен только один равносторонний треугольник с длинами 1+1
<pre>
для 2: 2+2;2+1 = 2 варианта
для 3: 3+3;3+2;3+1
2+2 = 4 варианта
для 4: 4+4;4+3;4+2;4+1
3+3;3+2 = 6 вариантов
для 5: 5+5;5+4;5+3;5+2;5+1
4+4;4+3;4+2
3+3 = 9 вариантов
12
16
20
25
и так далее.
</pre>
|
|
|
|
Добавлено: Сб янв 23, 2010 09:23 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
chess, a вот эту программку не прогоните через свой METER?
Код: : q3" ( n -- q ) 0 over 1 do \ j = 1 .. n over i - 0 do \ i = 0 .. n-j i j min + loop loop swap drop ;
EDIT: уже не надо
chess, a вот эту программку не прогоните через свой METER?
[code] : q3" ( n -- q ) 0 over 1 do \ j = 1 .. n over i - 0 do \ i = 0 .. n-j i j min + loop loop swap drop ; [/code]
EDIT: уже не надо
|
|
|
|
Добавлено: Сб янв 23, 2010 01:52 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
chess писал(а): forther писал(а): a вот как я сделал: Выглядит кратко, но при ближайшем рассмотрении очень медленный вариант. сравним варианты: Код: : forther 1000 q3 ; : chess 1000 Q3 ;
REQUIRE METER ~CHESS\TASK\METER.F
STARTLOG METER forther METER chess лог Код: 521252451 521555310 5688 5553 Ok что и требовалось доказать.
бесспорно!
интересно, а аналитическое решение кто нибудь покажет?
[quote="chess"][quote="forther"]a вот как я сделал: [/quote] Выглядит кратко, но при ближайшем рассмотрении очень медленный вариант. сравним варианты:
[code]: forther 1000 q3 ; : chess 1000 Q3 ;
REQUIRE METER ~CHESS\TASK\METER.F
STARTLOG METER forther METER chess[/code] лог [code]521252451 521555310 5688 5553 Ok[/code] что и требовалось доказать.[/quote]
бесспорно!
интересно, а аналитическое решение кто нибудь покажет?
|
|
|
|
Добавлено: Сб янв 23, 2010 01:28 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
Если вдуматься, то для каждой пары существует гипотетичеких 2(A+B)-1... вариантов треугольников с длиной стороны С,
Остается исключить не подходящие и повернутые (повторяющиеся в разлчной ротации тройки чисел) треугольники.
Так для случая когда стороны A и B равны 1, - имеем равносторонний треугольник.
Если вдуматься, то для каждой пары существует гипотетичеких 2(A+B)-1... вариантов треугольников с длиной стороны С,
Остается исключить не подходящие и повернутые (повторяющиеся в разлчной ротации тройки чисел) треугольники.
Так для случая когда стороны A и B равны 1, - имеем равносторонний треугольник.
|
|
|
|
Добавлено: Сб янв 23, 2010 01:14 |
|
|
|
|