|
Nice job.
For a signed 64-bit value, because you use make negative numbers positive, there is a single negative value that the code will not convert properly, and that is -2^63. The largest positive signed value is +2^63 - 1. That issue is not difficult to fix by making a special case for that one negative value. Your code currently does not handle that case.
You can convert a 64-bit number to a string using the C-runtime strtoull function, or using strtoll if the number is signed. However, I saw your comment regarding performance.
There is a faster algorithm to convert an integer number to decimal digits in the book "Semi-Numerical Methods" by Donald Knuth. Initially, the number is converted to octal digits, which is a trivial conversion, and then the octal number is converted to base 10. There are no divides in the algorithm. I will post the algorithm if I have time. After that conversion, groups of three digits can be processed as in your code. Note, the Knuth algorithm will provide decimal values, not ASCII decimal digits, although of course converting to ASCII is trivial.
The routine cannot fail, therefore it should return type void. There is no need to pass back the same buffer address that is passed in.
The code will only work with ASCII characters. It would be easy to convert the code to output other character sets, so that is not a big deal.
Of course, this only works for English, but I realize it would require a different implementation for other languages, and that is beyond the scope of your article.
Again, nice job.
|
|
|
|
|
Bill_Hallahan wrote: Nice job.
Thanks.
Bill_Hallahan wrote: he largest positive signed value is +2^63 - 1
You are correct.
Bill_Hallahan wrote: There is a faster algorithm to convert an integer number to decimal digits in the book "Semi-Numerical Methods" by Donald Knuth.
I'd have to see it. Not that my routine is heavily optimized, but I seriously doubt it's faster going the route you mentioned. Every decent CPU in the world has a math co-processor. And while division is slower than multiplication and bit shifting hacks, it can't be as slow as converting string data (internally) to a different base (externally). That's actually a misnomer since the computer doesn't care about that away, base representations are for human convenience. The CPU does not process octal, etc.
That being said, I'm sure I could optimize this a lot more if I really wanted to. Haven't had the need yet.
Bill_Hallahan wrote: The routine cannot fail, therefore it should return type void. There is no need to pass back the same buffer address that is passed in.
Nope. It returns the string so it can be called inline. It's a C trick us old farts like to do on occasion to pretend we're in C++.
Bill_Hallahan wrote: The code will only work with ASCII characters. It would be easy to convert the code to output other character sets, so that is not a big deal.
Have at it!
Jeremy Falcon
modified 14-May-14 22:16pm.
|
|
|
|
|
Jeremy Falcon wrote: Bill_Hallahan wrote: he largest positive signed value is +2^63 - 1
You are correct.
That wasn't my point. The point was that the code outputs a wrong string value for the value 0x8000000000000000. This is a bug.
The full text of what I wrote is:
For a signed 64-bit value, because you use make negative numbers positive, there is a single negative value that the code will not convert properly, and that is -2^63. The largest positive signed value is +2^63 - 1. That issue is not difficult to fix by making a special case for that one negative value. Your code currently does not handle that case.
Jeremy Falcon wrote: Bill_Hallahan wrote: The routine cannot fail, therefore it should return type void. There is no need to pass back the same buffer address that is passed in.
Nope. It returns the string so it can be called inline. It's a C trick us old farts like to do on occasion to pretend we're in C++.
Ah, that makes sense. Most of the C-runtime calls that take a buffer do that too, including the strtoull function, which could be used in the code, albeit I gather you measured it and it's slower.
Jeremy Falcon wrote: I'd have to see it. Not that my routine is heavily optimized, but I seriously doubt it's faster going the route you mentioned. Every decent CPU in the world has a math co-processor. And while division is slower than multiplication and bit shifting hacks, it can't be as slow as converting string data (internally) to a different base (externally). That's actually a misnomer since the computer doesn't care about that away, base representations are for human convenience. The CPU does not process octal, etc.
The code is doing a conversion to base 10 digits now. Each index you calculate to look up the appropriate string is a base 10 digit. Knuth's algorithm was designed to avoid the repeated divide by powers of 10. The octal conversion is trivial because a binary number is an octal number - groups of three bits form a digit from 0 to 7. I see you wrote a basic article on binary, so I am sure you realize that. The shifting and masking is extremely fast.
Also, you state that all decent processors have a divide. If you define a decent processor as one that has a divide, you are right, but the Knuth code will be fast on ARM, MIPs, Z80s, and other processors that are inexpensive and very useful, particularly in embedded work.
With a fast divide instruction, I'm not sure if Knuth's algorithm is worth it. I already have python code that converts a number to a text string. (I have this because I once worked with text-to-speech). That also uses the simple divide by 10 method. I'm going to code that in C and time it.
I am really surprised that using strtoull and then subtracting '0' (48) from each ASCII digit and using that as an index isn't faster than the code you wrote. Again, the code is now calculating each base10 digit, it just uses the digit as an index and then throws it away. I would expect the C routine to use optimal algorithms and take advantage of Intel parallel instructions (SSE1 and SSE2 instructions) that a C compiler does not generate.
Update:
I just noticed that Windows doesn't implement the C99 functions for 64-bit integers, at least not with Visual Studio 2008's standard installation. The Microsoft functions are:
_strtoi64, _wcstoi64, _strtoi64_l, _wcstoi64_l
The unsigned versions are:
_strtoui64, _wcstoui64, _strtoui64_l, _wcstoui64_l
|
|
|
|
|
Bill_Hallahan wrote: That wasn't my point. The point was that the code outputs a wrong string value for the value 0x8000000000000000. This is a bug.
You might want to read up on "how to talk to people" and "sarcasm". I'm fully aware of what the point was. 
Bill_Hallahan wrote: With a fast divide instruction, I'm not sure if Knuth's algorithm is worth it. I already have python code that converts a number to a text string. (I have this because I once worked with text-to-speech). That also uses the simple divide by 10 method. I'm going to code that in C and time it.
I am really surprised that using strtoull and then subtracting '0' (48) from each ASCII digit and using that as an index isn't faster than the code you wrote. Again, the code is now calculating each base10 digit, it just uses the digit as an index and then throws it away. I would expect the C routine to use optimal algorithms and take advantage of Intel parallel instructions (SSE1 and SSE2 instructions) that a C compiler does not generate.
I'm starting to think you haven't even looked at the code or article. It does not take a string and produce a number. Nor does it take a number and produce a string. It takes a number and produces a textual representation of a that number. Much like how you'd write out an amount on a check. What good would strtoull do me if my starting input is an unsigned long long to begin with?
Bill_Hallahan wrote: I just noticed that Windows doesn't implement the C99 functions for 64-bit integers, at least not with Visual Studio 2008's standard installation. The Microsoft functions are:
Awesome!
Jeremy Falcon
|
|
|
|
|
Jeremy Falcon wrote: Bill_Hallahan wrote: That wasn't my point. The point was that the code outputs a wrong string value for the value 0x8000000000000000. This is a bug.
You might want to read up on "how to talk to people" and "sarcasm". I'm fully aware of what the point was.
You might want to read up on communication - quoting an irrelevant partial sentence and then stating that it is correct doesn't come across as sarcasm in a text forum where someone has reported a bug to you.
I do realize there is no bug now, and that the magnitude is correct, but not because of your post. It just made no sense. I looked at the code again with fresh eyes today after a good nights sleep. Then I realize why you posted the way you did. Before that, frankly, I thought you were confused. I would rather you would have been straight with me and let me know that I was confused. Unlike some people here, I admit when I make mistakes.
Jeremy Falcon wrote: Bill_Hallahan wrote: With a fast divide instruction, I'm not sure if Knuth's algorithm is worth it. I already have python code that converts a number to a text string. (I have this because I once worked with text-to-speech). That also uses the simple divide by 10 method. I'm going to code that in C and time it.
I am really surprised that using strtoull and then subtracting '0' (48) from each ASCII digit and using that as an index isn't faster than the code you wrote. Again, the code is now calculating each base10 digit, it just uses the digit as an index and then throws it away. I would expect the C routine to use optimal algorithms and take advantage of Intel parallel instructions (SSE1 and SSE2 instructions) that a C compiler does not generate.
I'm starting to think you haven't even looked at the code or article. It does not take a string and produce a number. Nor does it take a number and produce a string. It takes a number and produces a textual representation of a that number. Much like how you'd write out an amount on a check. What good would strtoull do me if my starting input is an unsigned long long to begin with?
I looked at the code before posting. I named the wrong function, I meant a C function such as sprintf, that can convert a number to base 10. Then the base 10 digits can be converted to indices by subtracting '0' (48). This is the simplest and easiest to read implementation, even if not particularly fast. However, without timing it, I wouldn't assume it isn't fast. You apparently timed an implementation with "strings" because you posted about that in the article. I wonder what implementation with "strings" you timed.
Note, the algorithm I mentioned from the Knuth book can be done with any size integer data type, it need not use type char to store each digit, it an store them in an array of type int.
|
|
|
|
|
Bill_Hallahan wrote: albeit I gather you measured it and it's slower.
Try again when you learn how to program man. Returning a char * that's already buffered compared to a void is not slower. If I had to allocate two buffers you'd be correct, but since you didn't look at the code you're trying to improve you ain't yo.
Don't get me wrong, I'm all about improving code. Just make sure you're know what you're talking about first. It's a simple request. That is all.
Jeremy Falcon
|
|
|
|
|
Jeremy Falcon wrote: Bill_Hallahan wrote: albeit I gather you measured it and it's slower.
Try again when you learn how to program man. Returning a char * that's already buffered compared to a void is not slower. If I had to allocate two buffers you'd be correct, but since you didn't look at the code you're trying to improve you ain't yo.
Don't get me wrong, I'm all about improving code. Just make sure you're know what you're talking about first. It's a simple request. That is all.
Jeremy, your last sentence is ironic, because you did not know what I was talking about. In your defense, the meaning is a bit ambiguous, and because I named the wrong function, it was hard to get the right meaning. However, such errors are compounded by incomplete quotes, which also hide the true meaning of text. That quote isn't even a complete sentence - I usually quote entire paragraphs unless the rest isn't relevant.
Here is what I wrote: Ah, that makes sense. Most of the C-runtime calls that take a buffer do that too, including the strtoull function, which could be used in the code, albeit I gather you measured it and it's slower.
I meant you possibly measured the strtoull function. That function name was an error I made, I meant to put the name of a function that went from an unsigned 64-bit integer to a string. I expect you timed that because you explicitly wrote that you used an implementation with "strings" in the article, and you sped up the code 310% by changing the implementation. Perhaps you used sprintf, or something else, to convert the number to base 10 digits?
modified 17-May-14 5:08am.
|
|
|
|
|
Bill_Hallahan wrote: albeit I gather you measured it and it's slower.
And since I already know where you're going to go with this, I realize the CPU will have to execute a couple more instructions when assigning a value and returning it regardless if it's a pre-allocated memory address being pointed to or not. Everybody knows this. You're not providing me anything useful at all.
Consider the average CPU is running at 2.7 BILLION cycles per second. Do you really think two instructions will make a bit of difference when they take something like 0.00000000135 of a second to both execute? Hell no.
Anything else that's pointless you'd like to mention?
Jeremy Falcon
|
|
|
|
|
Jeremy Falcon wrote: Bill_Hallahan wrote: albeit I gather you measured it and it's slower.
<layer>And since I already know where you're going to go with this, I realize the CPU will have to execute a couple more instructions when assigning a value and returning it regardless if it's a pre-allocated memory address being pointed to or not. Everybody knows this. You're not providing me anything useful at all.
Consider the average CPU is running at 2.7 BILLION cycles per second. Do you really think two instructions will make a bit of difference when they take something like 0.00000000135 of a second to both execute? Hell no.
Anything else that's pointless you'd like to mention?
I responded to the duplicate message you posted with the same content. To summarize that other message, you didn't understand what I meant at all, possibly partially because you didn't quote the full sentence that I wrote, and thus lost much important context, or possibly because it was ambiguous and had an erroneous function name in my sentence.
Either way, absolutely everything in your reply had nothing to do with my intended meaning, which should be obvious to you if you go read the full quote (in my previous reply to this duplicate, or in the original post where I wrote it), with the knowledge that you wrote about an implementation with "strings" in your article, which you must have timed since you stated the performance improvement was 310%.
modified 17-May-14 5:34am.
|
|
|
|
|
Yeah I quit reading with my full attention when things get pointless. I prefer usable criticism that's constructive by someone who knows what they're talking about. So if I didn't quote the exact words you want to see to make you happy, then that's life pal. You can see a shrink about it, but even he might tell you to learn to program before trying to trash someone else who actually does. 
Jeremy Falcon
|
|
|
|
|
Jeremy, I know how to program, I've been doing it for 35 years. You are confusing a tired person making mistakes with a lack of knowledge and experience, and your comment is disrespectful towards someone you do not know.
I now realize from your last post that you are confusing a technical review with someone trashing you. In my post, I referred to code and the algorithm, not to you. And, at least one thing I wrote is correct.
All you had to write is, "your wrong, it works", and I would have re reviewed the code again, and realized my error. You actually did that with the issue of the return-type of the function, and I agreed immediately.
And, you wrote about improving performance. If you care about performance, I gave you some useful advice. I even offered the code. After looking the cycle times for the integer divide instruction for the Pentium IV processor mentioned in your article, I now realize that the algorithm I proposed would result in a huge speedup.
An 32-bit integer divide instruction takes about 387 cycles on an Intel X9650 processor. It's about the same number of cycles on both a 32-bit and the 64-bit architecture. Of course, caching issues and bus speeds are a factor for the speed of a program too, but based on that number of cycles, the algorithm in Seminumerical algorithms should be much faster than the divide algorithm used in the current code. And, the Pentium IV processor takes at least as many cycles as the 9650 for an integer divides, if not more.
The Pentium IV is a 32-bit processor, so it will take more than a single divide instruction to do a 64-bit divide.
On the more modern core i5 processors, an integer divide is about 40 cycles, so the algorithm you use might be fast enough on those. I suspect it will still be slower than the algorithm in the book, but I don't know that for sure. On a Pentium IV, the processor you mention in your article, the better algorithm will be significantly faster.
Again, it's the base 10 conversion algorithm in "Seminumerical Algorithms" by Donald Knuth.
If you want, I'll post the fast base 10 conversion code here, and it will drop right into your code with little change. I am not trashing you by doing that. I would never do that. I wouldn't have started and ended my initial post with "Nice job" if I meant to trash you.
Best wishes
modified 26-May-14 1:40am.
|
|
|
|
|
This is just a courtesy message to let you know I didn't read this nor will I. No longer wasting time on it. Have a nice life.
Jeremy Falcon
|
|
|
|
|
For anyone else who uses this code, beware of these two issues. Jeremy, I really do hope you read this so you fix the code.
-------------------------------------------------
The following number overruns the array szWord.
-7,777,777,777,777,777,777
This is within range of a signed 64-bit values.
The array szWord to contain the output string before it is copied to the passed buffer is currently 225 character in length. (I redownloaded the code, and double-checked that I didn't bump the keyboard and change this - it is 225). I also viewed the rendered text in the debugger.
char szWord[225] = {0};
The program doesn't crash with this value when I run the program, but I do get the wrong output text. An array overrun might act differently with different compilers, so you might or might not get the same result, but the array is definitely too short for the correct string, which is:
"negative seven quintillion seven hundred seventy-seven quadrillion seven hundred seventy-seven trillion seven hundred seventy-seven billion seven hundred seventy-seven million seven hundred seventy-seven thousand seven hundred seventy-seven"
That string is 240 characters long. (That text is from a different program - so the words are not capitalized).
--------------------------------------------------
The value "900" with ordinal set to true produces the string:
Nine Hundred
It should be:
Nine Hundredth
If there is one or three ending zeros in the final three digits, ordinals work, it doesn't work when there are two zeros at the end of the number.
modified 5-Jun-14 20:42pm.
|
|
|
|
|
|
Yup, that's me. Always been a programmer, but in the past couple of years took up acting. Which is awesome.
Jeremy Falcon
|
|
|
|
|
|
Yeah, I decided make an update and join last year an add 64-bit support. 
|
|
|
|
|
how to represent 1000.25 ????
Ninety-eight percent of the thrill comes from knowing that the thing you designed works, and works almost the way you expected it would. If that happens, part of you is in that machine.
|
|
|
|
|
renjith_sree wrote: how to represent 1000.25 ????
Since floating point operations can be slower than unsigned integer ones, I decided the best thing to do is not implement the decimal point conversion. However, this can be easily achieved in code by breaking a part the integral portions before and after the decimal place and calling GetNumWord() twice.
|
|
|
|
|
So, my question is: can you give us the function you wrote in PHP? I would love to incorprate this into a site I'm working on.
|
|
|
|
|
Nah, it's long since gone.  However, you can still use the C program over the web. How, exactly did you want to implement this?
Jeremy Falcon
|
|
|
|
|
Hmm... I'm not terribly familiar with C. Would it work on a Unix box?
Very simply, a site I run has an article series feature. That is, multiple articles are grouped together. At the beginning of each article, I'm doing a mysql_num_rows and dynamically assigning a page number to each article. Then I am printing the page number on the article: "This is article #4 of the X series."
So, I would like for the opening line of the article to say: "This is the fourth article in the X series." That's all I wanted to use it for.
|
|
|
|
|
Well, first and foremost. Do you have shell access to your site? That is, can you Telnet and/or SSH to it?
Jeremy Falcon
|
|
|
|
|
|
Sorry it took so long to get back to you on this.
But, if you have SSH access you'll need to take the existing code and make a CGI program out of it (so it'll return its output to STDOUT) and compile it on the server. Then, the simplest way to implement it into your site would be to use a SSI call to it.
Jeremy Falcon
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
