nedoPC.org

Community of electronics hobbyists established in 2002

...
Atom Feed | View unanswered posts | View active topics It is currently 23 Nov 2020 22:32



Reply to topic  [ 6 posts ] 
Быстрое умножение и деление на степень двойки 
Author Message
Retired

Joined: 03 Aug 2003 23:37
Posts: 1479
Location: Moscow
Reply with quote
Давайте думать о быстрых алгоритмах умножения и деления уравновешенного троичного числа на степень двойки. Мне стало известно, что такой алгоритм уже разработан в штатах и это меня как-то настораживает :D

Если про умножение есть кое-какие идеи, то вот оносительно деления ничего в голову не приходит.

_________________
Extreme Entertainment


16 Nov 2005 02:08
Profile
Retired

Joined: 03 Aug 2003 23:37
Posts: 1479
Location: Moscow
Reply with quote
Post 
Неужели ни кто ничего не может предложить ? :-?

_________________
Extreme Entertainment


19 Dec 2005 14:55
Profile
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18966
Location: Silicon Valley
Reply with quote
Post 
Mac Buster wrote:
Неужели ни кто ничего не может предложить ? :-?


Обозначим троичные сдвиги так:
>>> троичный сдвиг вправо (равносильно делению на 3)
<<< троичный сдвиг влево (равносильно умножению на 3)

Тогда можно записать:
2*T = 3*T-T = (T<<<1)-T
4*T = 3*T+T = (T<<<1)+T
10*T = 9*T+T = (T<<<2)+T

А вот с делением такие фокусы уже не пройдут :(

_________________
:eugeek: https://twitter.com/Shaos1973


20 Dec 2005 20:21
Profile WWW
Retired

Joined: 03 Aug 2003 23:37
Posts: 1479
Location: Moscow
Reply with quote
Post 
Shaos wrote:
Тогда можно записать:
2*T = 3*T-T = (T<<<1)-T
4*T = 3*T+T = (T<<<1)+T
10*T = 9*T+T = (T<<<2)+T

Да, примерно об этом я писал выше.

Quote:
А вот с делением такие фокусы уже не пройдут :(

Универсального решения я пока не нашёл, а выделение частных случаев занимает слишком много времени :-?

_________________
Extreme Entertainment


21 Dec 2005 00:46
Profile
Novelist

Joined: 20 Oct 2005 19:46
Posts: 34
Reply with quote
Post 
Shaos wrote:
А вот с делением такие фокусы уже не пройдут :(

Деление немного можно ускорить если, выполнять сдвиг делимого и делителя на количество нулевых младших разрядов делителя, а потом выполнять деление полученного делимого на полученный делитель


22 Dec 2005 06:40
Profile
Admin
User avatar

Joined: 09 Jan 2003 00:22
Posts: 18966
Location: Silicon Valley
Reply with quote
Автор Тунгуски в 2009 году предложил делить на 2 путём умножения на число .PPPPPP... (что есть 0.5):
Code:
A B C D / 2
-----------
  A B C . D
    A B . C D
 +    A . B C D
-----------------
[0, A, A+B, A+B+C].[B + C + D, C+D, D]

_________________
:eugeek: https://twitter.com/Shaos1973


29 May 2020 20:50
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 6 posts ] 

Who is online

Users browsing this forum: No registered users and 5 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.