electro-music.com   Dedicated to experimental electro-acoustic
and electronic music
 
    Front Page  |  Radio
 |  Media  |  Forum  |  Wiki  |  Links
Forum with support of Syndicator RSS
 FAQFAQ   CalendarCalendar   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   LinksLinks
 RegisterRegister   ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in  Chat RoomChat Room 
 Forum index » Clavia Nord Modular » G2 Building Blocks
Division (binary restoring method)
Post new topic   Reply to topic Moderators: Nord Modular Editors
Page 1 of 1 [2 Posts]
View unread posts
View new posts in the last week
Mark the topic unread :: View previous topic :: View next topic
Author Message
Tim Kleinert



Joined: Mar 12, 2004
Posts: 1148
Location: Zürich, Switzerland
Audio files: 7
G2 patch files: 236

PostPosted: Fri Aug 21, 2015 9:00 am    Post subject: Division (binary restoring method)
Subject description: customizable fast and realtime implementations
Reply with quote  Mark this post and the followings unread

cheerios,

As I'm moving on from the G2 platform, I've decided to skim through my folders containing tons of doodles and experiments and publish the ones that actually do something Laughing that might be useful.

As we all know, the G2 sadly lacks a dedicated division module. The cheapest and simplest way to patch it is via the Goldschmidt convergence algorithm, which requires merely two mixers and a multiplier in a feedback arrangement. It's really neat and produces full precision results. (IIRC, it's published here somewhere.)

But the Goldschmidt algorithm unfortunately has a few drawbacks. Being a convergence method, the calculation time is variable and highly dependent on the numerical size of numerator and denominator. Also, there is no built-in flagging of the final result. These issues can make it unsuitable for patches that require predictability of computation time and availability of the result.

The following patch is a G2 implementation of an algorithm harking back to the early days of computing, also known as the binary restoring division algorithm It is obviously more expensive, but has some big advantages in that it has a predictable calculation time, flags the result and also is very customizable.

The calculation time is directly related to the numeric resolution of the result. Eg., a 8 bit precision quotient requires 8 iterations, or 8 samples calculation time. In this way one can trade off precision against speed as one sees fit. (Just to clarify: the bit precision only pertains the resulting quotient. Numerator and denominator can be positive full-scale.)

The presented patch calculates the quotient to the full numerical resolution and thus updates itself every 23 samples. (The sign bit is not dealt with, the circuit only accepts positive numbers.) It also emits an one-sample spike trigger every time a new result has been calculated. It can be easily modified to not continuously auto-update by disconnecting the feedbacked comparator flag at the top, so the calculation can be externally triggered (with an one-sample spike). Also as stated, the calculation precision/speed can be easily modified by plugging in a correctly tuned constant into the empty comparator input. (Otherwise the circuit always calculates through the whole binary headroom down to zero.)

cheers,
t

EDIT: DSP usage of this circuit: 6.3% cycles, 10.2% memory


RestoDivision_TK.pch2
 Description:
predictable and customizable division using the binary restoring algorithm

Download
 Filename:  RestoDivision_TK.pch2
 Filesize:  1.8 KB
 Downloaded:  3652 Time(s)


Last edited by Tim Kleinert on Fri Aug 21, 2015 9:14 am; edited 3 times in total
Back to top
View user's profile Send private message
Tim Kleinert



Joined: Mar 12, 2004
Posts: 1148
Location: Zürich, Switzerland
Audio files: 7
G2 patch files: 236

PostPosted: Fri Aug 21, 2015 9:08 am    Post subject: Reply with quote  Mark this post and the followings unread

Addendum:

Another interesting property of the binary restoring method is that it can actually be implemented in real-time if you can sacrifice the DSP usage.

It's not at all taxing cycles-wise, but does eat up the zero-page memory fast.

Here's an example of a real-time 8 bit precision division. Basically an unravelling of the iterative loop. (we called that "speedcode" in the old C64 days Laughing ...)

EDIT: DSP usage of this circuit: 3.3% cycles (at control rate), 19.5% memory


RealtimeDivis_TK.pch2
 Description:
real-time division with 8 bit resolution, using a direct form of the binary restoring method

Download
 Filename:  RealtimeDivis_TK.pch2
 Filesize:  2.28 KB
 Downloaded:  3613 Time(s)

Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic Moderators: Nord Modular Editors
Page 1 of 1 [2 Posts]
View unread posts
View new posts in the last week
Mark the topic unread :: View previous topic :: View next topic
 Forum index » Clavia Nord Modular » G2 Building Blocks
Jump to:  

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 vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Forum with support of Syndicator RSS
Powered by phpBB © 2001, 2005 phpBB Group
Copyright © 2003 through 2009 by electro-music.com - Conditions Of Use