| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
Mul-table challenge
I was just coding another multiplication and once again I had to code a mul-table generator. Somehow I felt like doing it as small as possible and settle this forever. The routine should create:
- function: int((x*x)/4)
- x = 0 to 511
- two tables: 512 low bytes and 512 high bytes
- no dependencies on previous zeropage or register settings
So far I managed to do it in 54 bytes (RTS not included), is anyone able to do a smaller version?
EDIT:
53 bytes now :) |
|
| |
Monte Carlos
Registered: Jun 2004
Posts: 359 |
; (x+1)^2=x^2+(2x+1)
; Always add the next odd number to the prev. square.
lda #<table
sta zptr
lda #>table
sta zptr+1 ;= 8byt
lda #0
sta add
sta add+1
tax
tay ;=8 byt
loop:
clc
adc add
sta (zptr),y
pha
iny
txa
adc add+1
sta (zptr),y
tax
pla
inc add
inc add
bne *+4
inc add+1
iny
bne loop ;= 25 byt
inc zptr+1
ldy zptr+1
cpy #>ende
ldy #0
bcc loop
rts;11 byt
; 8+8+25+11 = ges 52
;Greetings Monte Carlos
|
| |
Monte Carlos
Registered: Jun 2004
Posts: 359 |
Shit, i forgot the division by 4!!!!
Sorry!
|
| |
Monte Carlos
Registered: Jun 2004
Posts: 359 |
; (x+1)^2=x^2+(2x+1)
; Always add the next odd number to the prev. square.
lda #<table
sta zptr
lda #>table
sta zptr+1 ;= 8byt
lda #0
sta add
sta add+1
tax
tay ;=8 byt
loop:
clc
adc add
sta (zptr),y
pha
iny
txa
adc add+1
sta (zptr),y
tax
pla
inc add
inc add
bne *+4
inc add+1
iny
bne loop ;= 25 byt
inc zptr+1
ldy zptr+1
cpy #>ende
ldy #0
bcc loop
rts;11 byt
; 8+8+25+11 = ges 52
;Greetings Monte Carlos
|
| |
Monte Carlos
Registered: Jun 2004
Posts: 359 |
Shit, the post appeared two times!
It was the "back" button of Mozilla, which
caused submitting of an already submitted entry!
Stupid ;)
|
| |
WVL
Registered: Mar 2002
Posts: 902 |
those are 256 byte tables :) |
| |
Cruzer
Registered: Dec 2001
Posts: 1048 |
Graham, just post your code already. 53 bytes sounds good enough for me :) |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
I'll post the code later on. Don't want to destroy new ideas by infecting other peoples brains with my approach :) |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
I have always created those tables in basic.. |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
And wasted (1024-x) bytes... |
| |
tlr
Registered: Sep 2003
Posts: 1790 |
You didn't say it had to be reentrant or runnable in ROM so I assume selfmod is fine.
My routine is 42 bytes excluding the rts. :) |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
Graham: yeah, so my vector parts load 0.1 second slower, did you notice ? :( |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
Assuming that that table was the only one. |
| |
Ben
Account closed
Registered: Feb 2003
Posts: 163 |
Graham, please hold yourself from posting the answer a couple of days so I can give it a thought.. |
| |
tlr
Registered: Sep 2003
Posts: 1790 |
Quote: You didn't say it had to be reentrant or runnable in ROM so I assume selfmod is fine.
My routine is 42 bytes excluding the rts. :)
Ok, shaved another byte off. 41 bytes excluding rts. |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
42 bytes with 512 entries and not 256? |
| |
tlr
Registered: Sep 2003
Posts: 1790 |
Quote: 42 bytes with 512 entries and not 256?
Yes 512 entries. Shaved another 2 bytes. 39 bytes excluding rts. :) |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
Ok this is getting interesting :) Did you verify the resulting table against some basic generator?
10 FOR I=0 TO 511
20 X = INT((X*X)/4)
30 XH = INT(X/256)
40 XL = X - (XH*256)
50 POKE 8192+I,XL
60 POKE 8704+I,XH
70 NEXT |
| |
tlr
Registered: Sep 2003
Posts: 1790 |
Quote: Ok this is getting interesting :) Did you verify the resulting table against some basic generator?
10 FOR I=0 TO 511
20 X = INT((X*X)/4)
30 XH = INT(X/256)
40 XL = X - (XH*256)
50 POKE 8192+I,XL
60 POKE 8704+I,XH
70 NEXT
No, but against a c-program.
Quick and dirty. ;)
Note also that the code is not in zeropage. If I put it there it will be shorter ofcourse, but that would be cheating in this case, no?
int main(int argc, char *argv[])
{
int i;
FILE *fp;
fp=fopen("bin","wb");
fputc(0x00,fp);
fputc(0xc8,fp);
for (i=0; i<512; ++i) {
int a;
a=i*i/4;
fputc((a&0xff),fp);
}
for (i=0; i<512; ++i) {
int a;
a=i*i/4;
fputc(((a>>8)&0xff),fp);
}
fclose(fp);
}
|
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
Nopes, no zeropage ofcourse. Hmm 39 bytes is really hard to believe, I managed to do it in 52 bytes now, or 51 if I use LAX #$00 (which is unstable on C128DCR). |
| |
tlr
Registered: Sep 2003
Posts: 1790 |
Quote: Nopes, no zeropage ofcourse. Hmm 39 bytes is really hard to believe, I managed to do it in 52 bytes now, or 51 if I use LAX #$00 (which is unstable on C128DCR).
I use no undocumented opcodes either. Tell me when you want to have a look at it.
We should probably wait a little while more though. There might come someone else with a 30 byte version. ;)
|
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
Ok 43 bytes now here... getting closer :) |
| |
tlr
Registered: Sep 2003
Posts: 1790 |
Quote: Ok 43 bytes now here... getting closer :)
:)
I just noticed I don't clear the decimal mode flag, but I'm guessing you don't either, right?
I wonder how different our routines can be if they are this close in size? It will be very interresting to compare. |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
Nopes, don't clear the decimal flag either. BTW: 38 bytes now :) |
| |
tlr
Registered: Sep 2003
Posts: 1790 |
Quote: Nopes, don't clear the decimal flag either. BTW: 38 bytes now :)
Ok... time to get back to the code then! ;) Good thing I have fresh coffee! |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
37 bytes... |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
36... |
| |
tlr
Registered: Sep 2003
Posts: 1790 |
Quote: 36...
You're scaring me... :) You are not depending on basic or kernal, are you? |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
No basic or kernal used :) |
| |
tlr
Registered: Sep 2003
Posts: 1790 |
37 bytes... :) Must think out of the box, must think out of the box... |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
I have to leave soon, should I post the 36 byte version? |
| |
tlr
Registered: Sep 2003
Posts: 1790 |
Sure! I'll post my 37 byte version, we can compare for fun, and someone else may shorten them further. ;) |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
Ok here it is:
ldx #$00
txa ; LAX #$00 would save one extra byte.
.db $c9
lb1: tya
adc #$00
ml1: sta multabhi,x
tay
cmp #$40
txa
ror
ml9: adc #$00
sta ml9+1
inx
ml0: sta multablo,x
bne lb1
inc ml0+2
inc ml1+2
clc ; Possible to remove this somehow?
iny
bne lb1
|
| |
tlr
Registered: Sep 2003
Posts: 1790 |
My mul-table: 37 bytes (excuding rts)
C000 A9 00 LDA #$00
C002 A8 TAY
C003 AA TAX
C004 C8 INY
C005 D0 06 BNE $C00D
C007 EE 15 C0 INC $C015
C00A EE 1A C0 INC $C01A
C00D 18 CLC
C00E 69 00 ADC #$00
C010 90 01 BCC $C013
C012 E8 INX
C013 99 FF C1 STA $C1FF,Y
C016 48 PHA
C017 8A TXA
C018 99 FF C3 STA $C3FF,Y
C01B 98 TYA
C01C 4A LSR A
C01D 68 PLA
C01E B0 E4 BCS $C004
C020 EE 0F C0 INC $C00F
C023 D0 DF BNE $C004
C025 60 RTS
|
| |
tlr
Registered: Sep 2003
Posts: 1790 |
Actually they are extremly different! :)
BTW, in my code multablow is $c200, and multabhighi $c400.
Thank you for the excellent competition! :) |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
Yupz, hard competition :) indeed quite different. I thought they'd look quite similar but they don't. Maybe there is a way to save another byte then... Anyway it was a good idea to do this compo, since without you doing the 42-39 byte versions I would not have investigated any more and just assumed that 53 bytes is the limit :) |
| |
Tch
Account closed
Registered: Sep 2004
Posts: 512 |
*imitating a crowd going berzerk*
Wohoo...we want more..heehaaaw!!! |
| |
Scout
Registered: Dec 2002
Posts: 1570 |
There's a dutch word for all of this: "bitneuken" :)
---
-= Silicon Ltd. =-
http://forum.siliconlimited.com |
| |
Bastet
Registered: Jul 2005
Posts: 88 |
You are nuts! ;) |
| |
Trash
Registered: Jan 2002
Posts: 122 |
Quote: Ok this is getting interesting :) Did you verify the resulting table against some basic generator?
10 FOR I=0 TO 511
20 X = INT((X*X)/4)
30 XH = INT(X/256)
40 XL = X - (XH*256)
50 POKE 8192+I,XL
60 POKE 8704+I,XH
70 NEXT
I atleast solved that basiclist in 18 bytes...
LDA #0
TAX
STA L, X
STA L + 256, X
STA H, X
STA H + 256, X
INX
BNE * - 13
:-/ |
| |
raven
Account closed
Registered: Jan 2002
Posts: 137 |
For converting that Basic prog correctly, the winner
is Trash ;)
I'm still stuck at 36 and my vision is getting
fuzzy so time for sleep..
|
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
trash, how does your TAX do X = INT((X*X)/4), then store separate lo/hi byte by the same A value ? |
| |
WVL
Registered: Mar 2002
Posts: 902 |
Quote: trash, how does your TAX do X = INT((X*X)/4), then store separate lo/hi byte by the same A value ?
read graham's basic list again :) |
| |
Trash
Registered: Jan 2002
Posts: 122 |
Quote: trash, how does your TAX do X = INT((X*X)/4), then store separate lo/hi byte by the same A value ?
Since cbm-basic initializes all variables to zero X=INT((X*X)/4) will always be zero therefore we can use a constant instead... |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
this is not my day |
| |
WVL
Registered: Mar 2002
Posts: 902 |
Quote: this is not my day
now guess how Graham feels :) |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
Trash: Basic only initializes when the variable is not already defined. Do X=<whatever> before RUN and constant 0 will not help you :P |
| |
Bastet
Registered: Jul 2005
Posts: 88 |
Look closer at that basic listing, Graham...
Does X increase? 'fraid it dosnt, so you can easily assume that x=0 *g* |
| |
Bastet
Registered: Jul 2005
Posts: 88 |
That will work out of the box:
1FORX=0TO511:Y=INT((x*x)/4)
2POKE8704+X,INT(y/256):POKE8192+X,Y-(PEEK(8704+x)*256):NEXTX
Thats 80 byte of basic code, tokenized and with header and footer of a standard file. *g*
Runs slow as hell but it works |
| |
enthusi
Registered: May 2004
Posts: 677 |
I was indeed considering to try to cut it a bit by using some kernal-mul-routine-call (as not beeing forbidden) but that was about the 54 byte version. 36 is out of the question :(
Too bad. But cudos for this nice fast challenge.
Next time please announce it before everyone else leaves to vacation or something so Im left alone with it for a looong time :)
|
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
@BastetFurry: Yeps X increases... For example, if you do X=16 before RUN, you'll have 16*16/4 = 64 and then 64*64/4 = 1024 etc. |
| |
TNT
Account closed
Registered: Oct 2004
Posts: 189 |
RUN clears all variables. You can circumvent that with GOTO <first_line> tho. |
