|
|
| Author |
Message |
apc
science forum beginner
Joined: 25 Jun 2006
Posts: 4
|
 Posted: Sun Jun 25, 2006 11:31 am Post subject:
is there an efficient algorithm for switching representation base?
|
|
|
Can someone please point me to a good algorithm for switching among
bases arbitrarily?
Thanks a lot in advance
apc. |
|
| Back to top |
|
 |
Virgil
science forum Guru
Joined: 24 Mar 2005
Posts: 5536
|
| Posted: Sun Jun 25, 2006 8:01 pm Post subject:
Re: is there an efficient algorithm for switching representation base?
|
|
|
In article <1151235076.683594.279260@b68g2000cwa.googlegroups.com>,
"apc" <andres.paniagua@web.de> wrote:
| Quote: | Can someone please point me to a good algorithm for switching among
bases arbitrarily?
Thanks a lot in advance
apc.
|
Do you mean bases of vector spaces, bases like binary or decimal for
expressing numbers values, bases of a topology, or some other sort of
bases?
'Base' and 'basis' can have different meanings in different mathematical
contexts, so we need to know which context you mean. |
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Sun Jun 25, 2006 10:50 pm Post subject:
Re: is there an efficient algorithm for switching representation base?
|
|
|
Virgil wrote:
| Quote: | In article <1151235076.683594.279260@b68g2000cwa.googlegroups.com>,
"apc" <andres.paniagua@web.de> wrote:
Can someone please point me to a good algorithm for switching among
bases arbitrarily?
Thanks a lot in advance
apc.
Do you mean bases of vector spaces, bases like binary or decimal for
expressing numbers values, bases of a topology, or some other sort of
bases?
|
.... bases of logarithms ...
| Quote: | 'Base' and 'basis' can have different meanings in different mathematical
contexts, so we need to know which context you mean.
|
"apc" should check out http://mathworld.wolfram.com/Base.html in any
case.
--- Christopher Heckman
] |
|
| Back to top |
|
|
Chip Eastham
science forum Guru
Joined: 01 May 2005
Posts: 412
|
| Posted: Mon Jun 26, 2006 12:30 am Post subject:
Re: is there an efficient algorithm for switching representation base?
|
|
|
apc wrote:
| Quote: | Can someone please point me to a good algorithm for switching among
bases arbitrarily?
Thanks a lot in advance
apc.
|
What you consider "good" probably depends on the
context.
Are you designing an algorithm in which the bases
are known in advance?
Or instead are the bases input at the same time as
the "digits" with respect to the "given" base?
Will this be implemented in a single-processor/single-
threaded environment with limited precision, or some
multiprocessor based supercomputing platform?
A simple approach is the obvious one of converting
the input string to binary representation and then
extracting digits modulo the desired base by integer
division with remainder. Word size is obviously an
important factor for speed if your target bases are
unusually large. Do you need more detail than this?
regards, chip |
|
| Back to top |
|
|
apc
science forum beginner
Joined: 25 Jun 2006
Posts: 4
|
| Posted: Mon Jun 26, 2006 5:44 am Post subject:
Re: is there an efficient algorithm for switching representation base?
|
|
|
Proginoskes wrote:
| Quote: | Virgil wrote:
In article <1151235076.683594.279260@b68g2000cwa.googlegroups.com>,
"apc" <andres.paniagua@web.de> wrote:
Can someone please point me to a good algorithm for switching among
bases arbitrarily?
Thanks a lot in advance
apc.
Do you mean bases of vector spaces, bases like binary or decimal for
expressing numbers values, bases of a topology, or some other sort of
bases?
... bases of logarithms ...
'Base' and 'basis' can have different meanings in different mathematical
contexts, so we need to know which context you mean.
"apc" should check out http://mathworld.wolfram.com/Base.html in any
case.
--- Christopher Heckman
]
Thank you for the link, I read the page but it doesn't give any |
information about algorithms for transforming a number from one system
of representation to another.
I will keep looking.
cheers.
apc. |
|
| Back to top |
|
|
apc
science forum beginner
Joined: 25 Jun 2006
Posts: 4
|
| Posted: Mon Jun 26, 2006 5:54 am Post subject:
Re: is there an efficient algorithm for switching representation base?
|
|
|
Chip Eastham wrote:
| Quote: | apc wrote:
Can someone please point me to a good algorithm for switching among
bases arbitrarily?
Thanks a lot in advance
apc.
What you consider "good" probably depends on the
context.
Are you designing an algorithm in which the bases
are known in advance?
Or instead are the bases input at the same time as
the "digits" with respect to the "given" base?
Will this be implemented in a single-processor/single-
threaded environment with limited precision, or some
multiprocessor based supercomputing platform?
A simple approach is the obvious one of converting
the input string to binary representation and then
extracting digits modulo the desired base by integer
division with remainder. Word size is obviously an
important factor for speed if your target bases are
unusually large. Do you need more detail than this?
regards, chip
Hi Chip, at this point I'm not taking into account the computing |
platform. What I'm looking for is an algorithm to transform the
representation of a whole positive number N in some base a into some
other base b. ie. N=4, a=2, b=3 Na=100 Nb=11. N, b, a will all be
integers. I already know the one you mention, but is there anything
better? By good I mean that it take as few simple steps as possible.
Thanks a lot
apc. |
|
| Back to top |
|
|
Robert B. Israel
science forum Guru
Joined: 24 Mar 2005
Posts: 2151
|
| Posted: Mon Jun 26, 2006 6:33 am Post subject:
Re: is there an efficient algorithm for switching representation base?
|
|
|
In article <1151301282.057399.220090@r2g2000cwb.googlegroups.com>,
apc <andres.paniagua@web.de> wrote:
| Quote: | Hi Chip, at this point I'm not taking into account the computing
platform. What I'm looking for is an algorithm to transform the
representation of a whole positive number N in some base a into some
other base b. ie. N=4, a=2, b=3 Na=100 Nb=11. N, b, a will all be
integers. I already know the one you mention, but is there anything
better? By good I mean that it take as few simple steps as possible.
Thanks a lot
apc.
|
IIRC Knuth "The Art of Computer Programming" volume II sec. 4.4
has a good discussion of this. The key phrase to look up is "radix
conversion".
Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada |
|
| Back to top |
|
|
Virgil
science forum Guru
Joined: 24 Mar 2005
Posts: 5536
|
| Posted: Mon Jun 26, 2006 6:45 am Post subject:
Re: is there an efficient algorithm for switching representation base?
|
|
|
In article <1151300688.624851.163550@p79g2000cwp.googlegroups.com>,
"apc" <andres.paniagua@web.de> wrote:
| Quote: | Proginoskes wrote:
Virgil wrote:
In article <1151235076.683594.279260@b68g2000cwa.googlegroups.com>,
"apc" <andres.paniagua@web.de> wrote:
Can someone please point me to a good algorithm for switching among
bases arbitrarily?
Thanks a lot in advance
apc.
Do you mean bases of vector spaces, bases like binary or decimal for
expressing numbers values, bases of a topology, or some other sort of
bases?
... bases of logarithms ...
'Base' and 'basis' can have different meanings in different mathematical
contexts, so we need to know which context you mean.
"apc" should check out http://mathworld.wolfram.com/Base.html in any
case.
--- Christopher Heckman
]
Thank you for the link, I read the page but it doesn't give any
information about algorithms for transforming a number from one system
of representation to another.
I will keep looking.
cheers.
apc.
|
If you are trying to convert numerals from one base to another, as in
decimal (base 10) to Hexadecimal (base 12) or vice versa: the following
is a general technique:
Split your number into integer and fractional parts
For the integer part, do integer division with remainder using your new
base number as divisor. Repeat using the previous quotient as your new
dividend until getting a final quotient of 0. Your successive
remainders will be the 'integer' digits of the number in the new base
when listed from right to left (first remainder is rightmost, last
remainder leftmost).
For the fractional part, assumed to be only a finite number of digits
long, multiply the proper fraction by the new base, splitting the
product into integer and fraction parts, and repeat on the new
fractional part until you either get a fractional part of zero or the
same fractional part as for some previous step.
If the fractional part of the original is non-terminating but repeating
before conversion, it is best to convert it into a proper fraction,
Integer divided by integer) first. This is always possible.
Then the iteration is to multiply the numerator by the base then split
the resulting (usually improper) fraction into an integer plus proper
fraction.
The integer parts taken on order from left to right are your fractional
digits. The process gives a terminating fractional part if some
fractional part is zero, otherwise is repeating. |
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Tue Jun 27, 2006 2:53 am Post subject:
Re: is there an efficient algorithm for switching representation base?
|
|
|
apc wrote:
| Quote: | Proginoskes wrote:
Virgil wrote:
In article <1151235076.683594.279260@b68g2000cwa.googlegroups.com>,
"apc" <andres.paniagua@web.de> wrote:
Can someone please point me to a good algorithm for switching among
bases arbitrarily?
Thanks a lot in advance
apc.
Do you mean bases of vector spaces, bases like binary or decimal for
expressing numbers values, bases of a topology, or some other sort of
bases?
... bases of logarithms ...
'Base' and 'basis' can have different meanings in different mathematical
contexts, so we need to know which context you mean.
"apc" should check out http://mathworld.wolfram.com/Base.html in any
case.
]
Thank you for the link, I read the page but it doesn't give any
information about algorithms for transforming a number from one system
of representation to another.
I will keep looking.
|
Can you give us a simple example of what you want to do? Until we know
what you're trying to do, no one can help.
--- Christopher Heckman |
|
| Back to top |
|
|
jt64@tele2.se
science forum beginner
Joined: 05 Jun 2006
Posts: 30
|
| Posted: Tue Jun 27, 2006 3:31 am Post subject:
Re: is there an efficient algorithm for switching representation base?
|
|
|
Below some code i wrote for switching between bases, i have no idea if
it is radix.
But it is a simple and fast algorithm.
<HTML>
<HEAD><TITLE>TEST</TITLE></HEAD>
<SCRIPT LANGUAGE="Javascript">
function decTOanybase(desiredbase,dec) {
btwo=1;
bnr=0;
unr=0;
document.write("CONVERSION TO ANYBASE<BR>","Decimal number to
convert=",dec);
while (btwo<dec){
btwo=btwo*desiredbase;
bnr++;
}
basestring="";
while (dec>0){
unr++;
set=0;
for(i=desiredbase;i>0;i--){
st=btwo*i;
if (dec>=st) {
dec=dec-st;
set=1;
basestring=basestring+i+",";
}
}
if(set==0 && dec!=0)basestring=basestring+0+",";
btwo=btwo/desiredbase;
}
while (bnr>=unr){
basestring=basestring+0+",";
unr++;
}
document.write("<BR>BASE ",desiredbase," = ",basestring," ");
}
//MAIN
decTOanybase(16,1024);
</SCRIPT>
<BODY><P>
//Of course it is simple to get code to support conversion *FROM*
anybase <BR>
//Just by recalculate input base to base 10 and go on from there
</BODY>
</HTML>
apc skrev:
| Quote: | Can someone please point me to a good algorithm for switching among
bases arbitrarily?
Thanks a lot in advance
apc. |
|
|
| Back to top |
|
|
Chip Eastham
science forum Guru
Joined: 01 May 2005
Posts: 412
|
| Posted: Tue Jun 27, 2006 12:12 pm Post subject:
Re: is there an efficient algorithm for switching representation base?
|
|
|
Robert Israel wrote:
| Quote: | In article <1151301282.057399.220090@r2g2000cwb.googlegroups.com>,
apc <andres.paniagua@web.de> wrote:
Hi Chip, at this point I'm not taking into account the computing
platform. What I'm looking for is an algorithm to transform the
representation of a whole positive number N in some base a into some
other base b. ie. N=4, a=2, b=3 Na=100 Nb=11. N, b, a will all be
integers. I already know the one you mention, but is there anything
better? By good I mean that it take as few simple steps as possible.
Thanks a lot
apc.
IIRC Knuth "The Art of Computer Programming" volume II sec. 4.4
has a good discussion of this. The key phrase to look up is "radix
conversion".
|
What Dr. Knuth points out in the passage cited by Robert Israel
is that converting (a nonnegative integer) from base a to base b
can proceed directly in one of two ways:
(1) Repeated integer division by b (with remainder) carried out
in radix a arithmetic (remainders yield the radix b "digits" from
least significant to most significant).
(2) Repeated multiplication by a (with accumulation) carried out
in radix b arithmetic (essentially Horner's method for evaluating
the polynomial in base a represented by the input, starting at
the most significant "digit" and proceeding to the least).
Since most computers have a particular facility at performing
binary arithmetic (radix 2), typically (2) is used to convert the
input from base a to binary, and (1) is used to produce output
in base b.
One optimization that Dr. Knuth points out is to work with the
"chunks" of digits that correspond to the largest power of a
base that fit in the machine word size. For example, if we
are converting from base 2 to base 3 (as suggested in the
original poster's reply above) and the machine word is a
byte, then we might simply accumulate the input in byte-
size chunks (256 = 2^ and output the ternary digits in
blocks of five (243 = 3^5), using procedure (1) above as
implemented in byte arithmetic.
regards, chip |
|
| Back to top |
|
|
apc
science forum beginner
Joined: 25 Jun 2006
Posts: 4
|
| Posted: Thu Jun 29, 2006 12:54 pm Post subject:
Re: is there an efficient algorithm for switching representation base?
|
|
|
Robert Israel wrote:
| Quote: | In article <1151301282.057399.220090@r2g2000cwb.googlegroups.com>,
apc <andres.paniagua@web.de> wrote:
Hi Chip, at this point I'm not taking into account the computing
platform. What I'm looking for is an algorithm to transform the
representation of a whole positive number N in some base a into some
other base b. ie. N=4, a=2, b=3 Na=100 Nb=11. N, b, a will all be
integers. I already know the one you mention, but is there anything
better? By good I mean that it take as few simple steps as possible.
Thanks a lot
apc.
IIRC Knuth "The Art of Computer Programming" volume II sec. 4.4
has a good discussion of this. The key phrase to look up is "radix
conversion".
Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
|
Thank you very much for the pointer, I should've thought of it myself.
I dug it up and am looking into it. |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Sat Jan 10, 2009 3:27 am | All times are GMT
|
|
Bankruptcy | Loans | Loans and Credit Cards | Boston Moving Company | Garcia Marquez
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
