- 1
- 2
- 3
- 4
- 5
BoxOfIndex =[0,0,0,1,1,1,2,2,2,0,0,0,1,1,1,2,2,2,0,0,0,1,1,1,2,2,2,
3,3,3,4,4,4,5,5,5,3,3,3,4,4,4,5,5,5,3,3,3,4,4,4,5,5,5,
6,6,6,7,7,7,8,8,8,6,6,6,7,7,7,8,8,8,6,6,6,7,7,7,8,8,8]
Box = BoxOfIndex[i*9 +j]
1024-- 01.09.2013 11:36 # +4
bormand 01.09.2013 15:28 # 0
На месте он ;) На x86 это скомпилится в че-то типа: Настоящего умножения на 9 там точно не будет.
1024-- 01.09.2013 15:39 # +1
bormand 01.09.2013 15:56 # +3
kegdan 01.09.2013 16:05 # +1
(i * 86 >> 8) ==i/3
?
1024-- 01.09.2013 16:11 # +1
Это явно какая-то примерная магия. Оно на i=128 даёт 43, а надо 42, а для i=0..127 работает.
Кстати, можно использовать от 86 до 96, чтобы работало от 0 до 8
bormand 01.09.2013 16:16 # +1
Ну оно так и есть, но для небольших чисел обычно работает.
Проще всего представить это как вычисление floor(1/3 * x) через fixed point с 8 знаками после точки. 86 это приближенная запись 1/3, а сдвиг вправо - это floor.
bormand 01.09.2013 16:11 # +1
kegdan 01.09.2013 16:21 # +1
получается (i/3)*2^8>>8 = i/3 для малых чисел
bormand 01.09.2013 16:35 # +1
Да.
(i * (256/3)) / 256 наверное будет самой наглядной записью.
kegdan 01.09.2013 16:43 # 0
1024-- 01.09.2013 16:56 # 0
ceil(256/3) была самой краткой и наглядной (для меня)
Я же в своих размышлениях отклонился от истины. Поделил 86/2, получил 43 - простое и не 3 - удивился, думал, что дело в старших битах, раз был сдвиг. Но 1010110 не похоже на 3, оно похоже на 5. Потом осознал, что старшие биты помогли бы с умножением. Скажем, i*86>>8 было бы умножением на 5 для малых чисел. В итоге всё больше укреплялась в голове мысль, что это магия, а 86 - это в честь x86 :)
Оставался лишь вопрос: 256 (?) 86..90 = 3.
bormand 01.09.2013 15:24 # 0
Алгоритмами будешь решать или брутом?
kegdan 01.09.2013 16:00 # 0
Dummy00001 01.09.2013 16:24 # 0
интересно на сколько это помогло производительность. судя по синтаксису, это похоже на питон. пара делений большой разницы не сыграют. во-первых.
во-вторых, а зачем изгалятся и не сделать просто вложеные массивы?
kegdan 01.09.2013 16:27 # 0
предложите реализацию
bormand 01.09.2013 16:33 # +2
> предложите реализацию
Видимо вот это имеется в виду:
Dummy00001 01.09.2013 16:42 # 0
kegdan 01.09.2013 16:45 # 0
Dummy00001 01.09.2013 17:08 # 0
kegdan 01.09.2013 17:12 # +1
Я буквально сегодня начал читать "Язык программирования Ruby" от отца-основателя и у меня уже передозировка сахаром)