Re: OOT: negative numbers in any base
Re: OOT: negative numbers in any base
- Subject: Re: OOT: negative numbers in any base
- From: Michèle Garoche <email@hidden>
- Date: Sun, 11 Aug 2002 21:16:12 +0200
Hello Nathan,
Sorry for the delay in replying.
I think I've not phrased my problem accurately as usual:-)
I'm working on the Calculator in Building Cocoa Applications. I try to
extend it to handle any base recognized by the compiler. The calculator
works only with integers.
Digits entered by the user are accumulated in a buffer according to the
base:
X = X * radix +-X (+X if X positive, -X if X nC)gative)
Another buffer stores old X values when new one is entered. Then
computing is let to the compiler and the result is injected in first
buffer after storing its old values in second one. Thus my problem is
only with the display of numbers.
I already have a global routine to prepare the display for binaries:
NSString *ltob(unsigned long val)
{
// To display binary numbers
int i;
char buf[33];
for (i = 0; i < 32; i++)
{
buf[i] = (val & (1<<(31-i)) ? '1' : '0');
}
buf[32] = '\0';
for (i = 0; i < 32; i++)
{
if (buf[i] != '0')
{
return [NSString stringWithCString: buf + i];
}
}
return [NSString stringWithCString: buf + 31];
}
And another one to prepare the display for positive numbers in any other
base (except for 10, 16 and 8, where I used stringWithFormat directly):
NSString *nton(int val, int myRadix)
{
// To display other bases than default ones
if (val >= 0)
{
int length = 1;
int div = myRadix;
int val1 = abs(val);
int i = 0;
// Build the representation
char repr[myRadix];
while (i < myRadix)
{
repr[i] = (i > 9) ? 'A' - 10 + i : '0' + i;
i++;
}
// count the number of digits needed
while (val1 / div > 0)
{
length++;
div *= myRadix;
}
// Build the string
char str[length];
int tempLength = length;
str[length--] = '\0';
for ( ; length >= 0; length--)
{
str[length] = repr[val1 % myRadix];
val1 /= myRadix;
}
for (i = 0; i < tempLength; i++)
{
// Don't display leading zeros
if (str[i] != '0')
{
return [NSString stringWithCString: str + i];
}
}
// Case number equals 0
return [NSString stringWithCString: str + tempLength -1];
}
// Don't process negative numbers
return [NSString stringWithString: @"Undefined"];
}
If I want to handle negative numbers, obviously this routine doesn't
work, because of integers limits.
Example: max integer in some bases: 2^31-1
base 2: 1111111111111111111111111111111 (31 x)
negate: 10000000000000000000000000000001
base 3: 12112122212110202101 and not 22222222222222222222
base 8: 17777777777 and not 77777777777
negate: 20000000001
base 10: 2147483647
base 16: 7FFFFFFF and not FFFFFFFF
negate : 80000001
etc...
Example with -1 with stringWithFormat:
Hexa : FFFFFFFF
Octal: 37777777777
Hence my question: how the compiler build a negative number according to
the limits. Rephrased, it would have been how the compiler convert the
binary number obtained by negating a number into another base
representation according to the limits.
I've searched Cocoa doc, no answer. Then I've searched unix man pages,
no answer. Then Don directed me to some good URLS where I've refreshed
my maths (shame on me for forgetting almost anything on this topic and
many other ones - it was indeed one of my favourite one as a student and
in those times where computers could not handle more than 16 digits I
rewrote in Assembler basic math routines, inputs and outputs to handle
32 digits).
Yesterday, in desperation, I searched Darwin source code, Core
Foundation, etc.. If I understood well it's in a part of code that's
private at a very low level (not sure though, the code is way too
complicated for me to understand it well).
Basically, the algorithm would be:
1 - write the number in base R : this is already done
so I have N = bai x R ^ i I retain the ai as a string
2 - add to this string as many leading zeros as the maximum for the base
I can compute the number of digits needed to represent the maximum
number in the base, but...
3 - Search for the first non zero digit from the right, replace it with
R - a, replace all other ones with R - 1 - a
But, but, but... this is wrong because of the limits. For example in
octal:
-1 would be written as 77777777777 but the right answer is 37777777777
So, the question is how to take the limits into accounts in the
algorithm?
Le vendredi 9 aoC;t 2002, C 06:14 , Nathan Day a C)crit :
Not sure if this is what you are after but
-x = ~(x-1)
for example with an 8 bit -2
2 = b00000010
(2-1) = b00000001
~(2-1) = b11111110
alternatively
~(-x)+1 = x
-2 = b11111110
~(-2) = b00000001
~(-2)+1 = b00000010
it has the advantage that addition and subtraction can be done the same
way
5 - 2 = b00000101 + b11111110 = 5 + 254 = 259 = b100000011
but we only have eight bit so it's b00000011 = 3
On Thursday, August 8, 2002, at 03:54 AM, MichC(le Garoche wrote:
Hello,
Sorry for OOT.
Could someone tell me where I can find how the compiler build a
negative number? Some place on the web as I have no access to
specialized libraries, general (not only for binary numbers: I know
how to do it), and no too complicated as my math studies are far
behind me:-)
A simple case: say I enter 1 in base 10, then I negate the number, the
result displayed is -1 as the compiler knows how to write it. Now I
switch to base 3 (not balanced ternary), how can I build the result (I
know how I can build the result for positive numbers, and I know the
limits).
I thought of that way to do it, but not sure if it's the right one:
1 - store the digits in an int variable - done
2 - translate the number into binary string - done
3 - translate the binary string into decimal - to do
4 - translate the decimal into x base string - done
Nathan Day
http://homepage.mac.com/nathan_day/
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.