Integer Base Function

[Robbie Hatley]

Re: Integer Base Function

"Earl Purple" wrote:

Robbie Hatley wrote:
>

But there are certain features of C++ which I love so much that
I rarely use C anymore, except for firmware or tiny utility apps:

namespaces
std containers
std::string
std algorithms
std iterators
parameterized constructors
templates
functors

>
so if you like templates so much, and since your code is all inlined
anyway, why not make the function a template on its integral type?

I did. Probably around the same time as you were writing your post.
I also incorporated many of Frederick Gotham's nifty tips.

You can use numeric_limits to find out some of the information you need
about what type you have.

Yep, that's what I did.

Here's my updated version of my Base<>() function:

// Put this in a header file:

namespace YourNamespaceNa me
{

///////////////////////////////////////////////////////////////////////////
// //
// Base //
// Represent an integer in any base from 2 to 36. //
// //
///////////////////////////////////////////////////////////////////////////

template<typena me T>
std::string
Base
(
int base, // must be >= 2 and <= 36
int precision, // must be >= 1 and <= 63
T number, // must be >= min+5 and <= max-5 for type
bool leading_zeros = false // does user want leading zeros?
)
{
T const max = std::numeric_li mits<T>::max() - 5;
T const min = std::numeric_li mits<T>::min() + 5;
double largest = pow(base, precision) - 1;
if
(
base < 2 || base 36 // If base is out-of-range
|| precision < 1 || precision 63 // or precision is out-of-range
|| number < min || number max // or number is out-of-range
|| largest max // or base/precision combo is out-of-range
|| largest < number // or base/precision combo can't express number
)
{
return std::string("** *ERROR***"); // then return "***ERROR** *".
}

std::string repre = std::string("") ;
if (number < 0)
{
number = -number;
repre += '-';
}

T place = 1;
for (int i = 1; i <= precision - 1; ++i)
{
place *= base;
}

T value = 0;
const char digits[37] = "0123456789ABCD EFGHIJKLMNOPQRS TUVWXYZ";
bool first_non_zero = false;
for ( ; place 0; place /= base)
{
value = number / place;
if (value 0) first_non_zero = true;
if (leading_zeros || first_non_zero) repre += digits[value];
number -= value * place;
}
return repre;

} // end Base()

} // end namespace YourNamespaceNa me


--
Cheers,
Robbie Hatley
Tustin, CA, USA
lonewolfintj at pacbell dot net
(put "[usenet]" in subject to bypass spam filter)

http://home.pacbell.net/earnur/

[Frederick Gotham]

Re: Integer Base Function

Robbie Hatley posted:

I did. Probably around the same time as you were writing your post.
I also incorporated many of Frederick Gotham's nifty tips.

I've written such an alogrithm before, and made it ultra-efficient. (I
don't think many people here would like my code.) I'd post the code, but
it's embedded deep within some horrible template code.

Basically, I started off with the max value for an integer type, e.g.:

4294967295

And then I calculated the maximum power of the radix which is smaller
than the max value, i.e.:

1000000000 (assuming a radix of 10)


I would then take a value from the user, e.g.: 2533916891

I would divide the user's value by the max power; this would yield the
first digit. Then I would mod the user value with the radix, and then
divide the max power by the radix. Kind of like:

2533916891
1000000000 Yields 2


533916891
100000000 Yields 5

33916891
10000000 Yields 3

3916891
1000000 Yields 3

916891
100000 Yields 9

16891
10000 Yields 1

6891
1000 Yields 6

891
100 Yields 8

91
10 Yields 9

1
1 Yields 1


I went way way WAY overboard on the whole efficiency side of things
though, calculating as many stuff with template metaprogramming as I can.


--

Frederick Gotham

[Robbie Hatley]

Re: Integer Base Function

"Frederick Gotham" wrote:

2533916891
1000000000 Yields 2
>
533916891
100000000 Yields 5
>
33916891
10000000 Yields 3
>
3916891
1000000 Yields 3
>
916891
100000 Yields 9
>
16891
10000 Yields 1
>
6891
1000 Yields 6
>
891
100 Yields 8
>
91
10 Yields 9
>
1
1 Yields 1

If you look at my code, it's doing exactly the same thing.
Except that I use the word "base" instead of "radix", "place"
to mean base^(place-value-index), and "value" to mean digit * place.

See the "place /= base" in the for loop? It's doing the exact
thing you present in your chart above.

For example, user enters base=27, precision=30, number=3847566.
My error-checking makes sure precision is high enough that
base^precision number, which is true in this case.
Start with place = base ^ (precision - 1).
number/place == 0, place /= base;
number/place == 0, place /= base;
number/place == 0, place /= base;
... many more times ...

when place gets from 27^30 down to 27^4, I finally get a
non-zero result:

number is now 3847566 and place is now 27^4 == 531441.
digit = number/place = 3847566/531441 = 7, so print "7" and do
value = digit * place = 7 * 531441 = 3720087
number -= value;
place /= base;

number is now 127479 and place is now 27^3 == 19683.
digit = number/place = 127479/19683 = 6, so print "6" and do
value = digit * place = 6 * 19683 = 118098
number -= value;
place /= base;

number is now 9381 and place is now 27^2 = 729.
digit = number/place = 9381/729 = 12 ("C"), so print "C" and do
value = digit * place = 12 * 729 = 8748
number -= value;
place /= base;

number is now 633 and place is now 27^1 = 27.
digit = number/place = 633/27 = 23 ("N"), so print "N" and do
value = digit * place = 23 * 27 = 621
number -= value;
place /= base;

number is now 12 and place is now 27^0 = 1.
digit = number * place = 12 * 1 = 12 ("C"), so print "C" and do
value = digit * place = 12 * 1 = 12
number -= value;
place /= base;

number is now 0 and place is now 0. for-loop test fails.
return "76CNC";


The only major way I can see to make the algorithm more efficient
is to calculate the "precision" to be exactly what it needs to
be, intead of letting the user specify a number which may be way
too high, such as the user entering a precision of "40" when
the result is actually only going to have 5 27ary digits.

Perhaps something like:

if (!leading_zeros )
{
precision = static_cast<int >(floor((log(nu mber)/log(base))));
}


--
Cheers,
Robbie Hatley
Tustin, CA, USA
lonewolfintj at pacbell dot net
(put "[usenet]" in subject to bypass spam filter)

http://home.pacbell.net/earnur/

[Frederick Gotham]

Re: Integer Base Function

Robbie Hatley posted:

The only major way I can see to make the algorithm more efficient
is to calculate the "precision" to be exactly what it needs to
be, intead of letting the user specify a number which may be way
too high, such as the user entering a precision of "40" when
the result is actually only going to have 5 27ary digits.
>
Perhaps something like:
>
if (!leading_zeros )
{
precision = static_cast<int >(floor((log(nu mber)/log(base))));
}

To find out the amount of leading zeros, you could firstly find out the
maximum amount of digits for a type for a give radix. So if we assume a
radix of 10, and we have the following max value:

4294967295

Then our max digits is: 10

Then we take an input from the user, and calculate the max amount of
digits. Subtract the two numbers and we have the amount of leading zeros.

Here's a template if you're interested:


template< class T, T max, T radix, bool max_is_less_tha n_radix = (max <
radix) >
struct MaxDigits {

static T const val = 1 + MaxDigits<T,max / radix,radix>::v al;
};


template< class T, T max, T radix>
struct MaxDigits<T,max ,radix,true{

static T const val = 1;
};


#include <iostream>

int main()
{
std::cout << MaxDigits<unsig ned long,-1,10>::val;
}


--

Frederick Gotham

[Robbie Hatley]

Re: Integer Base Function

"Frederick Gotham" <fgothamNO@SPAM .comwrote:

Robbie Hatley posted:
>

The only major way I can see to make the algorithm more efficient
is to calculate the "precision" to be exactly what it needs to
be, intead of letting the user specify a number which may be way
too high, such as the user entering a precision of "40" when
the result is actually only going to have 5 27ary digits.

Perhaps something like:

if (!leading_zeros )
{
precision = static_cast<int >(floor((log(nu mber)/log(base))));
}

>
To find out the amount of leading zeros, you could firstly find out the
maximum amount of digits for a type for a give radix. So if we assume a
radix of 10, and we have the following max value:

The code I gave is calculating the precision, not the number of leading
zeros. The reason for the condition "if (!leading_zeros )" is because
if the user wants leading zeros, then I can't calculate precision;
I have to use the precision given by the user, if possible.

Example: user says, "display leading zeros, precision = 30, base= 27,
number=3847566" . Then the function has to display:

000000000000000 000000000076CNC

It's like seting width to 30 and fill-char to '0' when printing to
cout. Except, cout does't understand 27ary, so we have to fake it.

But if the user DOESN'T want leading zeros, and specifies a precision
of 30, the first 25 digits calculated will all be zeros! A major
waste of time.

So how do we know in advance how many digits are in Base<base>(numb er)?

Conceptually, the answer is: the integer part of log<base>(numbe r).

Since the std. lib. doesn't have log<base>, we have to use a bit
of algebra: log<base>(numbe r) = log<e>(number)/log<e>(base).
Since the std. lib. function for log<eis "log", we have:
precision = static_cast<int >(floor((log(nu mber)/log(base))));

The only problem I can see with that is, log only handles double,
so the precision may not be high enough if the user requests
long long ints. If we start the conversion just one digit too
far to the right, the "digit" might be 36, overflowing the
digits array, causing a general protection fault. So it's wise
to add 1. Won't hurt anything, and will prevent disaster:
precision = static_cast<int >(floor((log(nu mber)/log(base)))) + 1;


As for your templates, I must admit that at first glance I don't
understand them. That's some sort of tricky recursive
metaprogramming , isn't it? I'll have to study those when I have
more time, and see what they're doing. Thanks for posting them.


--
Cheers,
Robbie Hatley
Tustin, CA, USA
lonewolfintj at pacbell dot net
(put "[usenet]" in subject to bypass spam filter)

http://home.pacbell.net/earnur/