_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Nope. Still only one subtraction, but 3 comparisons. 80000 will be found at T8E4 and only needs one subtraction from the input value.

The main loop should look like this:
* Step #1) X_BYTES is stored in the X-reg and starts at the highest byte in its category to compare the
* table's hi-byte with the hex value hi-byte (i.e. LDX X_BYTES,Y where Y is the number of hex bytes in the input value)
* If table byte is greater than input byte, the X-reg is subtracted by the number of digits to get the next lower hi-byte from the table
* If the hi-bytes are equal, then a comparison of the next lower hex byte will need to be made until the table byte is less than input byte or the byte counter is zero
* Once the table hex byte is lower than the input byte, the subtraction can be made for all hex digits of the input value
* After the subtraction is made and the new value stored, the new value should have one less hex byte to deal with.
* The number of hex bytes is reduced by one and put into the Y-reg
* if Y-reg <> 0 then loop back to the first step


Here is the table that would be used for an 8-digit hex (max $FF FF FF FF FF FF FF FF)(20-digit decimal #).

INPUTHEXVAL DS 8

HEXDIGSLO DFB 09,00,#ONEHEX,#TWOHEX,#THREHEX,#FOURHEX
DFB #FIVEHEX,#SIXHEX,#SEVENHEX,#EIGHTHEX,#NINEHEX

HEXDIGSHI DFB 09,00,#<ONEHEX,#<TWOHEX,#<THREHEX,#<FOURHEX
DFB #<FIVEHEX,#<SIXHEX,#<SEVENHEX,#<EIGHTHEX,#<NINEHEX
X_BYTES HEX 00
DFB TWOHEX-ONEHEX ; 0A
DFB THREHEX-TWOHEX ; 2B
DFB FOURHEX-THREHEX ; 41
DFB FIVEHEX-FOURHEX ; 53
DFB SIXHEX-FIVEHEX ; 77
DFB SEVENHEX-SIXHEX ; 72
DFB EIGHTHEX-SEVENHEX ; A1
DFB NINEHEX-EIGHTHEX ; A8
DFB ENDTABLE-NINEHEX ; 50

* The "e" stands for the number of zeroes that follow (1e3 = 1000, 2e3 = 2000 .. etc )

ONEHEX EQU *
T1e1 HEX 0A
T2e1 HEX 14
T3e1 HEX 1E
T4e1 HEX 28
T5e1 HEX 32
T6e1 HEX 3C
T7e1 HEX 46
T8e1 HEX 50
T9e1 HEX 5A

T1e2 HEX 64
T2e2 HEX C8

TWOHEX EQU *
T3e2 HEX 2C,01
T4e2 HEX 90,01
T5e2 HEX F4,01
T6e2 HEX 58,02
T7e2 HEX BC,02
T8e2 HEX 20,03
T9e2 HEX 84,03

T1e3 HEX E8,03
T2e3 HEX D0,07
T3e3 HEX B8,0B
T4e3 HEX A0,0F
T5e3 HEX 88,13
T6e3 HEX 70,17
T7e3 HEX 58,1B
T8e3 HEX 40,1F
T9e3 HEX 28,23

T1e4 HEX 10,27
T2e4 HEX 20,4E
T3e4 HEX 30,75
T4e4 HEX 40,9C
T5e4 HEX 50,C3
T6e4 HEX 60,EA

THREHEX EQU *
T7e4 HEX 70,11,01
T8e4 HEX 80,38,01
T9e4 HEX 90,5F,01

T1e5 HEX A0,86,01
T2e5 HEX 40,0D,03
T3e5 HEX E0,93,04
T4e5 HEX 80,1A,06
T5e5 HEX 20,A1,07
T6e5 HEX C0,27,09
T7e5 HEX 60,AE,0A
T8e5 HEX 00,35,0C
T9e5 HEX A0,BB,0D

T1e6 HEX 40,42,0F
T2e6 HEX 80,84,1E
T3e6 HEX C0,C6,2D
T4e6 HEX 00,09,3D
T5e6 HEX 40,4B,4C
T6e6 HEX 80,8D,5B
T7e6 HEX C0,CF,6A
T8e6 HEX 00,12,7A
T9e6 HEX 40,54,89

T1e7 HEX 80,96,98

FOURHEX EQU *
T2e7 HEX 00,2D,31,01
T3e7 HEX 80,C3,C9,01
T4e7 HEX 00,5A,62,02
T5e7 HEX 80,F0,FA,02
T6e7 HEX 00,87,93,03
T7e7 HEX 80,1D,2C,04
T8e7 HEX 00,B4,C4,04
T9e7 HEX 80,4A,5D,05

T1e8 HEX 00,E1,F5,05
T2e8 HEX 00,C2,EB,0B
T3e8 HEX 00,A3,E1,11
T4e8 HEX 00,84,D7,17
T5e8 HEX 00,65,CD,1D
T6e8 HEX 00,46,C3,23
T7e8 HEX 00,27,B9,29
T8e8 HEX 00,08,AF,2F
T9e8 HEX 00,E9,A4,35

T1e9 HEX 00,CA,9A,3B
T2e9 HEX 00,94,35,77
T3e9 HEX 00,5E,D0,B2
T4e9 HEX 00,28,6B,EE

FIVEHEX EQU *
T5e9 HEX 00,F2,05,2A,01
T6e9 HEX 00,BC,A0,65,01
T7e9 HEX 00,86,3B,A1,01
T8e9 HEX 00,50,D6,DC,01
T9e9 HEX 00,1A,71,18,02

T1e10 HEX 00,E4,0B,54,02
T2e10 HEX 00,C8,17,A8,04
T3e10 HEX 00,AC,23,FC,06
T4e10 HEX 00,90,2F,50,09
T5e10 HEX 00,74,3B,A4,0B
T6e10 HEX 00,58,47,F8,0D
T7e10 HEX 00,3C,53,4C,10
T8e10 HEX 00,20,5F,A0,12
T9e10 HEX 00,04,6B,F4,14

T1e11 HEX 00,E8,76,48,17
T2e11 HEX 00,D0,ED,90,2E
T3e11 HEX 00,B8,64,D9,45
T4e11 HEX 00,A0,DB,21,5D
T5e11 HEX 00,88,52,6A,74
T6e11 HEX 00,70,C9,B2,8B
T7e11 HEX 00,58,40,FB,A2
T8e11 HEX 00,40,B7,43,BA
T9e11 HEX 00,28,2E,8C,D1

T1e12 HEX 00,10,A5,D4,E8

SIXHEX EQU *
T2e12 HEX 00,20,4A,A9,D1,01
T3e12 HEX 00,30,EF,7D,BA,02
T4e12 HEX 00,40,94,52,A3,03
T5e12 HEX 00,50,39,27,8C,04
T6e12 HEX 00,60,DE,FB,74,05
T7e12 HEX 00,70,83,D0,5D,06
T8e12 HEX 00,80,28,A5,46,07
T9e12 HEX 00,90,CD,79,2F,08

T1e13 HEX 00,A0,72,4E,18,09
T2e13 HEX 00,40,E5,9C,30,12
T3e13 HEX 00,E0,57,EB,48,1B
T4e13 HEX 00,80,CA,39,61,24
T5e13 HEX 00,20,3D,88,79,2D
T6e13 HEX 00,C0,AF,D6,91,36
T7e13 HEX 00,60,22,25,AA,3F
T8e13 HEX 00,00,95,73,C2,48
T9e13 HEX 00,A0,07,C2,DA,51

T1e14 HEX 00,40,7A,10,F3,5A
T2e14 HEX 00,80,F4,20,E6,B5

SEVENHEX EQU *
T3e14 HEX 00,C0,6E,31,D9,10,01
T4e14 HEX 00,00,E9,41,CC,6B,01
T5e14 HEX 00,40,63,52,BF,C6,01
T6e14 HEX 00,80,DD,62,B2,21,02
T7e14 HEX 00,C0,57,73,A5,7C,02
T8e14 HEX 00,00,D2,83,98,D7,02
T9e14 HEX 00,40,4C,94,8B,32,03

T1e15 HEX 00,80,C6,A4,7E,8D,03
T2e15 HEX 00,00,8D,49,FD,1A,07
T3e15 HEX 00,80,53,EE,7B,A8,0A
T4e15 HEX 00,00,1A,93,FA,35,0E
T5e15 HEX 00,80,E0,37,79,C3,11
T6e15 HEX 00,00,A7,DC,F7,50,15
T7e15 HEX 00,80,6D,81,76,DE,18
T8e15 HEX 00,00,34,26,F5,6B,1C
T9e15 HEX 00,80,FA,CA,73,F9,1F

T1e16 HEX 00,00,C1,6F,F2,86,23
T2e16 HEX 00,00,82,DF,E4,0D,47
T3e16 HEX 00,00,43,4F,D7,94,6A
T4e16 HEX 00,00,04,BF,C9,1B,8E
T5e16 HEX 00,00,C5,2E,BC,A2,B1
T6e16 HEX 00,00,86,9E,AE,29,D5
T7e16 HEX 00,00,47,0E,A1,B0,F8

EIGHTHEX EQU *
T8e16 HEX 00,00,08,7E,93,37,1C,01
T9e16 HEX 00,00,C9,ED,85,BE,3F,01

T1e17 HEX 00,00,8A,5D,78,45,63,01
T2e17 HEX 00,00,14,BB,F0,8A,C6,02
T3e17 HEX 00,00,9E,18,69,D0,29,04
T4e17 HEX 00,00,28,76,E1,15,8D,05
T5e17 HEX 00,00,B2,D3,59,5B,F0,06
T6e17 HEX 00,00,3C,31,D2,A0,53,08
T7e17 HEX 00,00,C6,8E,4A,E6,B6,09
T8e17 HEX 00,00,50,EC,C2,2B,1A,0B
T9e17 HEX 00,00,DA,49,3B,71,7D,0C

T1e18 HEX 00,00,64,A7,B3,B6,E0,0D
T2e18 HEX 00,00,C8,4E,67,6D,C1,1B
T3e18 HEX 00,00,2C,F6,1A,24,A2,29
T4e18 HEX 00,00,90,9D,CE,DA,82,37
T5e18 HEX 00,00,F4,44,82,91,63,45
T6e18 HEX 00,00,58,EC,35,48,44,53
T7e18 HEX 00,00,BC,93,E9,FE,24,61
T8e18 HEX 00,00,20,3B,9D,B5,05,6F
T9e18 HEX 00,00,84,E2,50,6C,E6,7C

T1e19 HEX 00,00,E8,89,04,23,C7,8A

NINEHEX EQU *
T2e19 HEX 00,00,D0,13,09,46,8E,15,01
T3e19 HEX 00,00,B8,9D,0D,69,55,A0,01
T4e19 HEX 00,00,A0,27,12,8C,1C,2B,02
T5e19 HEX 00,00,88,B1,16,AF,E3,B5,02
T6e19 HEX 00,00,70,3B,1B,D2,AA,40,03
T7e19 HEX 00,00,58,C5,1F,F5,71,CB,03
T8e19 HEX 00,00,40,4F,24,18,39,56,04
T9e19 HEX 00,00,28,D9,28,3B,00,E1,04

T1E20 HEX 00,00,10,63,2D,5E,C7,6B,05

ENDTABLE EQU *


The table was smaller than I thought it would be at just under 900 bytes.
I will give everyone a chance to play with the table before posting my own code.
I left a kind of easter egg in this table. Can you spot it?
Happy programming!

Shouldn't that be a $46 (going by the patterns ... I have no clue of the nuts-and-bolts of what you're doing)?

Similarly, should be $84, $03, unless I'm completely lost.

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)

Another typo (7A vs. 71):
T9e9 HEX 00,1A,71,18,02

Don't forget to apply the other 2 corrections above.

Yep. Those are typos. That's one way to tell if anyone is playing with the table.
Typos have been fixed in the table in the previous post.

Some are questioning what to do with the table. The previous way of subtracting with using a table was to keep subtracting a power-of-10 number from a remaining total to get each digit of a number. i.e. to get 9000 out of $2328, $3e8 is subtracted from $2328, 9 times. And since $3e8 = 1000 , 9 x 1000 = 9000.

This table offers a lookup for all the powers of 10 values so the subtraction, only has to be done once for each power of 10. Which is basically the same as 9 x 1000 = 1 x 9000.

I have come across some quirks when using this table, but each quirk can be handled very quickly before entering any search or calculation loops. The ultimate goal is to reduce the amount of time spent in a loop to reduce the overall time for the conversion.

In a few upcoming posts, I will present these quirks and how to overcome them with, sometimes, a single calculation.

That may be true for rendering for display, but I can make a strong case for the need for speed in numeric conversion.

This is a bit of a long saga, so please bear with me.

Prior to 2015, I was tinkering with the XGameStation AVR development kit.

http://www.ic0nstrux.com/xgs-avr-8-bit- ... ent-system

The supplied workflow consisted of compiling code written in C on a PC and downloading the binary result to the board. Someone developed a BASIC system which tokenized programs on the PC to be executed by an interpreter on the target board. In the quest for something more interactive, I ported a FORTH interpreter I had written to the AVR, but I was not happy with it and began writing an old-school (line numbers required) BASIC interpreter in C.

Late in the summer of 2015, I joined a couple of local makerspaces.

At one of them, I began dabbling with the Arduino. Mistakenly believing that it was a drag-and-drop environment resembling Lego Mindstorms, I had been shunning it before. Seeing it in action convinced me otherwise. Development stopped with the XGS kit.

Sometime in 2016, I decided to learn to program in Python. After studying it on my own for months, I took one of the classes at the makerspace.

Python was popular. Arduino was popular. But we cannot directly program an Arduino in Python. "I can fix that," I thought. With 32K words of flash memory for the code and 2K of static RAM, it was obvious that the AVR 328P microcontroller will not support much of an interpreter. But if a program is compiled, only the parts of the language which are actually used need to be present. 32K is actually a lot of instructions for an AVR but 2K of RAM seemed quite limiting.

The thought of implementing two Pythonic features, dynamic typing and variable precision integers was an irresistable challenge, so I started writing a compiler. Because there was a Commodore 128 on display at the makerspace I could use for testing, I initially chose to target the 6502 instruction set.

The FLEX operating system converts an integer to decimal by repeated subtraction of powers of ten kept in a small table. This approach does not scale up to big numbers so the classic digit extraction using repeated division by ten method was implemented.

My "moonshot" milestone was compiling and running a program to calculate Fibonacci numbers. It was downright amazing to see that many digits come out of a 6502. It was not particularly fast, however, and I did not analyze it to see where the time was being spent but just accepted that as a result of the amount of data involved.

https://talk.dallasmakerspace.org/t/pro ... r/18852/60

Further experience with the compiler began to show that RAM usage was not as high as initially feared. Maybe compiling for the AVR can be practical after all. Because I had previously begun implementing floating point code on the 6800 and AVR, these platforms were added as future targets for the compiler.

The acquisition of a used Briel Altair 8800micro clone added the 8080 to the target list; what could possibly be cooler than compiling Python code for an Altair?

At this, a friend began lobbying intensely for a version to target the TI 99/4A.

While lurking on the AtariAge forums, which has an active section discussing the TI, I came upon this challenge:

https://atariage.com/forums/topic/17925 ... s-problem/

In a nutshell, find a power of seven which contains six consecutive '7' digits. The conversation evolved to discussing the fastest way to do it. The task consists of three CPU-intensive parts: big number arithmetic, converting the number to ASCII decimal and searching the result for a substring. All three are standard equipment in Python. I could implement them in assembly language as part of a Python run-time library and still claim the fastest solution written entirely in a high-level language.

https://talk.dallasmakerspace.org/t/pro ... /18852/288



Work was done to be able to compile and run (more accurately, crawl) this program. The result gave the correct answer, but was *extremely* slow. Superficial analysis showed that number conversion was by far the slowest of the three parts.

The compiled Python solution of the Sevens problem took about 22 billion CPU cycles on a 6502, meaning that a 1 MHz machine would have to grind on it for around six hours.

A search for a faster way to perform the conversion led me to the Double Dabble algorithm.

https://en.wikipedia.org/wiki/Double_dabble

I have not yet mustered the motivation to implement Double Dabble for big numbers. Versions of the algorithm to convert integers of 1, 2 and 4 bytes on several processors including the 6502 were posted here:

https://talk.dallasmakerspace.org/t/pro ... /18852/323

The code in the OP pointed out a potential optimization - shift only one byte of the number to be converted at a time instead of shifting the entire thing.

I have since come up with another approach to the Sevens problem using BCD arithmetic without doing any multiplication. The Borland dialect of Pascal turned out to be the ideal implementation language because it provided a way to treat an array of bytes as a string as well as an array. It also comes with a substring search. That program completes almost instantaneously on my relatively slow netbook.

Some day, I will have compilers for both Python and Pascal generating TI 9900 code so that I can race them against the other solutions. But the crucial part of an implementation with Python is a fast way to do the conversion.

I would look at it as four subtractions where you just throw away the result of three of them.

I'm not sure that there's a case where you'd ever be concerned about whether you're doing a comparison or a subtraction. Both take machine cycles (usually the same number of cycles) and bytes of code, and there are enough other things affecting the overall efficiency (be it time or space) that a mere count of subtraction versus comparison operations won't tell you whether one algorithm is more efficient than another.


I can see how the task could be broken down that way, though there are two important things that could be made more explicit in that description: the question involves searching a decimal string for a decimal substring, and the first part of the answer is binary big number arithemtic. When looked at in that way, the question, "why not do your big number arithemtic in decimal?" perhaps becomes more obvious. (Or, possibly, "Why not look for six consecutive '7' digits in the hexadecimal representation of the string?")

_________________
Curt J. Sampson - github.com/0cjs

I suspect that the OP found the problem in a math puzzle book, thought, "I can do that!" and coded up a solution using the tool he had available, BASIC. He then posted his experience to the forum not intending or expecting that it would become an efficiency competition.

Why hamstring the solution by specifying artificial and unnecessary constraints? It is like asking, "What is the best way to get from Dallas to Philadelphia for the Monday night game?" If fastest or cheapest is not specified, you get more variety in responses. Flying is the quickest. Driving is the cheapest. Rail, bus, horse and foot cannot get there in time.

My solution in Pascal keeps the number as unpacked binary BCD. Unpacked to eliminate repeated packing and unpacking. Binary to eliminate masking. A "pchar" (pointer to char) variable provides an efficient way to traverse the number. The Pascal "pos" function searches for six consecutive binary seven bytes within the number.

I got big binary number to ASCII decimal conversion working with the Double Dabble algorithm.

Instead of over 22 billion machine cycles with the divide by ten for each digit method, the Sevens problem completes in a little over 103.2 million cycles. That is not unlike going from a bicycle to an airliner.

There is still some room for optimization. Namely the fact that numbers up to 100 bytes in size do not result in a string over 255 characters long, so calculations can be done using single-byte values. I'm thinking maybe up to a doubling of the speed.

The original divide by 10 for each digit method took over 22 billion cycles.

The first double-byte double dabble implementation took $626D28A 103207562 cycles.

The implementation of a single-byte double dabble mode for numbers 100 bytes or less took $59D709A 94204058 cycles. This was more than I was expecting.

After some more optimization, it dropped to $59D47D6 94193622 cycles.

What this is trying to say is that the decimal conversion is no longer a large majority of the time. To see how this broke down:

Omitting the string search took $5974C0C 93801484 cycles.


Omitting the string search and the decimal conversion took $3F55E03 66412035 cycles.


What this means is that the multiplication code needs another look. I know it can be improved.

Definitely keep the loop to skip leading zeroes. It is a major win when you have a low magnitude number in many bytes.

Your inner loop will be faster using X instead of Y for non-indirect indexing.

Ah, you mean in case FORMAT_BUF is in ZP, right?

You have NUM in the zero page and should be using X instead of Y to access it.

Edit: Never mind. You are doing lda NUM,Y, never sta NUM,Y where there is a difference.