Go Back > Extra Stuff > Miscellaneous Math

Thread Tools
Old 2005-01-18, 00:27   #1

2·32·5·67 Posts
Default need C implementation of divb(r,k)

i am trying to implement the algorithms in "DETECTING PERFECT POWERS
IN ESSENTIALLY LINEAR TIME" by dj bernstein, and a required function is divb(r,k), which is apparently found in "The art of computer programming, volume 2: seminumerical algorithms" ex 4.3.1-16, but since i do not have access to this book i am stuck without it.

if someone could provide the alogrithm, an implementation or a link either of these it would be greatfully appreciated.
  Reply With Quote
Old 2005-01-18, 01:58   #2
ColdFury's Avatar
Aug 2002

26·5 Posts

Too bad you didn't ask yesterday since I have the book at home.

Maybe if you explain what the function is supposed to do, we could help.
ColdFury is offline   Reply With Quote
Old 2005-01-18, 02:12   #3
P90 years forever!
Prime95's Avatar
Aug 2002
Yeehaw, FL

3·5·499 Posts

Is this what you are looking for?
Prime95 is online now   Reply With Quote
Old 2005-01-18, 08:44   #4
akruppa's Avatar
Aug 2002

2,467 Posts

Text of exercise 4.3.1-16:

(Short division.) Design an algorithm that divides a nonnegative n-place integer (u_{n-1} ... u_1 u_0)_b by v, where v is a single-precision number (that is, 0 < v < b), producing the quotient (w_{n-1} ... w_1 w_0)_b and remainder r.

Sounds like grammer-school division by a single digit (in base b) integer - shouldn't be hard to do.

akruppa is offline   Reply With Quote
Old 2005-01-18, 23:14   #5

28×37 Posts

Thanks akruppa, that was exactly what I was lookin for, hmm wonder if any libraries here in NZ have a copy of that book...

also the bignum thing looks interesting, I could use it in the future to handle bigger numbers.
  Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Wii U, good concept, bad implementation? jasong jasong 6 2013-10-23 18:34
SQUFOF implementation alpertron Factoring 15 2010-04-12 19:16
ECM/FPGA Implementation rdotson Hardware 12 2006-03-26 22:58
RSA implementation flava Programming 12 2004-10-26 03:51
Different types of factoring, implementation dsouza123 Factoring 12 2003-08-08 11:35

All times are UTC. The time now is 17:22.

Sat May 8 17:22:40 UTC 2021 up 30 days, 12:03, 0 users, load averages: 3.50, 3.34, 3.08

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.