Posts: 1,407
Threads: 117
Joined: Dec 2002
Moneo:
My program uses huge (more than 64K) arrays, as does Blitz's. In the IDE they are activated with /AH, don't know what is the equivalent switch in BC.
Antoni
Posts: 3,368
Threads: 195
Joined: Jan 2003
Preprocessing is cheating!
Question!!!!!! QUESTION!!!!!!! The user inputs 20,000 numbers and tests if any of them exist out of the other 20,000 numbers in the file?!?!?!?!
Wouldn't it be better just to use TWO files, then???!!!!
Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."
Visit www.neobasic.net to see rubbish in all its finest.
Posts: 788
Threads: 53
Joined: Nov 2002
the /ah switch is the same in bc. And you should compile with vbdos. It's better with LONGs.
oship me and i will give you lots of guurrls and beeea
Posts: 788
Threads: 53
Joined: Nov 2002
Quote:BTW: I don't understand why you set up a two dimensional array, and why you use the values 16384 and 16383. What are you trying to do?
*****
End the challenge first and i'll explain.
oship me and i will give you lots of guurrls and beeea
Posts: 3,368
Threads: 195
Joined: Jan 2003
WAIT!!!!!!!!!
Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."
Visit www.neobasic.net to see rubbish in all its finest.
Posts: 788
Threads: 53
Joined: Nov 2002
I did a benchmark between mine and antonis, i think he'll agree that they're very fair. Here they are.
Code: defint a-z
const KEYMIN& = 0&
const KEYMAX& = 99999&
const VALIDKEY = -1
declare sub loadKeyTable ( filename as string )
declare function checkKey% ( keyToCheck as long )
'$dynamic
dim shared keyTable( KEYMAX \ 16384&, 16383 ) as integer
'$static
''
'' Entry point
''
dim result as integer
dim keyToCheck as long
dim indxa as integer, indxb as integer
dim tmrIni as single, tmrEnd as single
''
'' This is not part of the main program
'' it's just setup.
''
loadKeyTable "valid.txt"
keyToCheck = 13
tmrIni = timer
for i = 0 to 31999
indxa = keyToCheck \ 16384&
indxb = keyToCheck and 16383&
result = keyTable( indxa, indxb )
indxa = keyToCheck \ 16384&
indxb = keyToCheck and 16383&
result = keyTable( indxa, indxb )
indxa = keyToCheck \ 16384&
indxb = keyToCheck and 16383&
result = keyTable( indxa, indxb )
indxa = keyToCheck \ 16384&
indxb = keyToCheck and 16383&
result = keyTable( indxa, indxb )
indxa = keyToCheck \ 16384&
indxb = keyToCheck and 16383&
result = keyTable( indxa, indxb )
indxa = keyToCheck \ 16384&
indxb = keyToCheck and 16383&
result = keyTable( indxa, indxb )
indxa = keyToCheck \ 16384&
indxb = keyToCheck and 16383&
result = keyTable( indxa, indxb )
indxa = keyToCheck \ 16384&
indxb = keyToCheck and 16383&
result = keyTable( indxa, indxb )
indxa = keyToCheck \ 16384&
indxb = keyToCheck and 16383&
result = keyTable( indxa, indxb )
indxa = keyToCheck \ 16384&
indxb = keyToCheck and 16383&
result = keyTable( indxa, indxb )
next i
tmrEnd = timer
print "Blitz code does" + str$(clng( 32000#*10# / (tmrEnd-tmrIni) )) + " searches per second"
'' :::::::::
'' name: loadKeyTable
'' desc: Loads a bunch of valid keys
'' note: This is to be run BEFORE starting to time
''
'' :::::::::
defint a-z
sub loadKeyTable ( filename as string ) static
dim currKey as long
dim keysRead as long
dim keysInFile as long
dim i as integer, j as integer
dim indxa as integer, indxb as integer
open filename for input as #1
''
'' Clear table and load keys
''
for i = 0 to KEYMAX \ 16384&
for j = 0 to 16383
keyTable( i, j ) = 0
next j
next i
while ( not eof( 1 ) )
input #1, currKey
if ( (currKey < KEYMIN) or (currKey > KEYMAX) ) then
print "Error: Invalid key in file..."
end
end if
''
'' Put key in table
''
indxa = currKey \ 16384&
indxb = currKey and 16383&
keyTable( indxa, indxb ) = VALIDKEY
wend
close #1
end sub
And Antonis
Code: DECLARE FUNCTION funFirstPrime% (threshold%)
DEFINT A-Z
CONST empty = -1&
CONST QBOFFSET = 16636
'-----------------------------setup------------------------------------
filename$ = "valid.txt"
OPEN filename$ FOR INPUT AS #1
codecnt = 0
WHILE NOT EOF(1)
codecnt = codecnt + 1
INPUT #1, CODE$
WEND
TABLESIZE = funFirstPrime(codecnt)
REDIM SHARED CODES(-QBOFFSET TO TABLESIZE - QBOFFSET) AS LONG
FOR I = LBOUND(CODES) TO UBOUND(CODES)
CODES(I) = empty
NEXT
SEEK 1, 1
WHILE NOT EOF(1)
INPUT #1, CODE&
KEYINDEX = (CODE& MOD TABLESIZE)
WHILE CODES(KEYINDEX - QBOFFSET) <> empty
IF CODES(KEYINDEX - QBOFFSET) = CODE& THEN PRINT "Repeated code in input": END
IF KEYINDEX = TABLESIZE THEN
KEYINDEX = 0
ELSE
KEYINDEX = KEYINDEX + 1
END IF
WEND
CODES(KEYINDEX - QBOFFSET) = CODE&
WEND
CLOSE
'--------------------------main loop-------------------------------------
dim result as integer
dim tmrIni as single, tmrEnd as single
CODE& = 13
tmrIni = timer
for i = 0 to 31999
KEYINDEX = (CODE& MOD TABLESIZE)
WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
IF KEYINDEX = TABLESIZE THEN
KEYINDEX = 0
ELSE
KEYINDEX = KEYINDEX + 1
END IF
WEND
result = CODES(KEYINDEX - QBOFFSET) = CODE&
KEYINDEX = (CODE& MOD TABLESIZE)
WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
IF KEYINDEX = TABLESIZE THEN
KEYINDEX = 0
ELSE
KEYINDEX = KEYINDEX + 1
END IF
WEND
result = CODES(KEYINDEX - QBOFFSET) = CODE&
KEYINDEX = (CODE& MOD TABLESIZE)
WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
IF KEYINDEX = TABLESIZE THEN
KEYINDEX = 0
ELSE
KEYINDEX = KEYINDEX + 1
END IF
WEND
result = CODES(KEYINDEX - QBOFFSET) = CODE&
KEYINDEX = (CODE& MOD TABLESIZE)
WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
IF KEYINDEX = TABLESIZE THEN
KEYINDEX = 0
ELSE
KEYINDEX = KEYINDEX + 1
END IF
WEND
result = CODES(KEYINDEX - QBOFFSET) = CODE&
KEYINDEX = (CODE& MOD TABLESIZE)
WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
IF KEYINDEX = TABLESIZE THEN
KEYINDEX = 0
ELSE
KEYINDEX = KEYINDEX + 1
END IF
WEND
result = CODES(KEYINDEX - QBOFFSET) = CODE&
KEYINDEX = (CODE& MOD TABLESIZE)
WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
IF KEYINDEX = TABLESIZE THEN
KEYINDEX = 0
ELSE
KEYINDEX = KEYINDEX + 1
END IF
WEND
result = CODES(KEYINDEX - QBOFFSET) = CODE&
KEYINDEX = (CODE& MOD TABLESIZE)
WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
IF KEYINDEX = TABLESIZE THEN
KEYINDEX = 0
ELSE
KEYINDEX = KEYINDEX + 1
END IF
WEND
result = CODES(KEYINDEX - QBOFFSET) = CODE&
KEYINDEX = (CODE& MOD TABLESIZE)
WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
IF KEYINDEX = TABLESIZE THEN
KEYINDEX = 0
ELSE
KEYINDEX = KEYINDEX + 1
END IF
WEND
result = CODES(KEYINDEX - QBOFFSET) = CODE&
KEYINDEX = (CODE& MOD TABLESIZE)
WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
IF KEYINDEX = TABLESIZE THEN
KEYINDEX = 0
ELSE
KEYINDEX = KEYINDEX + 1
END IF
WEND
result = CODES(KEYINDEX - QBOFFSET) = CODE&
KEYINDEX = (CODE& MOD TABLESIZE)
WHILE CODES(KEYINDEX - QBOFFSET) <> CODE& AND CODES(KEYINDEX - QBOFFSET) <> empty
IF KEYINDEX = TABLESIZE THEN
KEYINDEX = 0
ELSE
KEYINDEX = KEYINDEX + 1
END IF
WEND
result = CODES(KEYINDEX - QBOFFSET) = CODE&
next i
tmrEnd = timer
print "Antonis code does" + str$(clng( 32000#*10# / (tmrEnd-tmrIni) )) + " searches per second"
END
FUNCTION funFirstPrime (threshold)
tp30 = INT((threshold * 1.3))
IF tp30 / 2 = tp30 \ 2 THEN
tp30 = tp30 + 1
END IF
c = tp30 - 2
IF c < 1 THEN
c = 1
END IF
t2& = threshold * 2&
DO
c = c + 2
FOR z = 3 TO SQR(c)
ind = -1
IF c / z = c \ z THEN
ind = FALSE
EXIT FOR
END IF
NEXT z
IF ind THEN
IF (c - 3) / 4 = INT((c - 3) / 4) OR c > t2& THEN
funFirstPrime = c
EXIT DO
END IF
END IF
LOOP
END FUNCTION
After running each 8 times during the exact same conditions my best was 6301538 and Antonis was 2925714.
oship me and i will give you lots of guurrls and beeea
Posts: 1,407
Threads: 117
Joined: Dec 2002
Quote:Come on, the hard part is stuffing the codes into as little memory as possible. That's the whole idea of the challenge!
Oh, well, so you were asking for this!:
Code: 'user password validation using a bit array
'Antoni Gual 2003
'-----------------------------setup------------------------------------
DEFINT A-Z
DIM pwrsof2(15)
FOR i = 0 TO 14: pwrsof2(i) = 2 ^ i: NEXT: pwrsof2(15) = &H8000
filename$ = "valid.txt"
OPEN filename$ FOR INPUT AS #1
DIM codes(16636)
WHILE NOT EOF(1)
LINE INPUT #1, A$
code& = VAL(A$)
byte = code& \ 16
bit = code& MOD 16
codes(byte) = codes(byte) OR pwrsof2(bit)
WEND
CLOSE
DO
DO
INPUT "enter your code"; usr$
IF usr$ = "" THEN END
code& = VAL(usr$)
IF code& > 0 AND code& < 99999 THEN EXIT DO
PRINT "code must be in range 0 to 99999"
LOOP
byte = code& \ 16
bit = code& MOD 16
IF codes(byte) AND pwrsof2(bit) THEN
PRINT "Accepted"
ELSE
PRINT "Rejected"
END IF
LOOP
END
Blitz:
I agree Your code was faster. Maybe as fast than this new one
Antoni
Posts: 788
Threads: 53
Joined: Nov 2002
Yeah, that one is much much faster. Although it's basically the same as my code except you used a bit array to be able to use a static array. If you put dynamic before it runs the same speed as mine. But yeah, it's faster then mine now. cheeeataarr!
oship me and i will give you lots of guurrls and beeea
Posts: 1,956
Threads: 65
Joined: Jun 2003
Quote:Preprocessing is cheating!
Question!!!!!! QUESTION!!!!!!! The user inputs 20,000 numbers and tests if any of them exist out of the other 20,000 numbers in the file?!?!?!?!
Wouldn't it be better just to use TWO files, then???!!!!
AGA,
In the range of 0 to 99999 there are 100,000 possible codes, of which there are 20,000 identified as valid in the VALID.TXT file. The idea is to read the valid codes and store them in memory somehow for later validation for each of the user input codes.
Yes, that's pre-processing, but it saves you from having to scan the entire VALID.TXT file everytime the user gives you a code.
*****
Posts: 788
Threads: 53
Joined: Nov 2002
Alright, since we're playing it like that. Eat this Antoni, 36 million compared to your 24
Code: ''
'' If i had to chose i'd use a number in the range
'' 0 to 32767 for effciency. If the number was
'' bigger then that i wouldn't use qb.
'' Use the /ah option or you won't be able to compile
'' or run.
''
''
defint a-z
const KEYMIN& = 0&
const KEYMAX& = 99999&
declare sub loadKeyTable ( filename as string )
declare function checkKey% ( keyToCheck as long )
dim shared PowerOf2( 15 ) as integer
dim shared keyTable( (KEYMAX+1) \ 16 ) as integer
''
'' Entry point
''
dim indx as integer
dim result as integer
dim keyToCheck as long
dim tmrIni as single, tmrEnd as single
''
'' This is not part of the main program
'' it's just setup.
''
loadKeyTable "valid.txt"
keyToCheck = 13
tmrIni = timer
for j = 0 to 99
for i = 0 to 31999
result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
result = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
next i
next j
tmrEnd = timer
print "Blitz code does" + str$(clng( 32000#*10#*100# / (tmrEnd-tmrIni) )) + " searches per second"
'' :::::::::
'' name: checkKey
'' desc: Checks if a key is valid
''
'' :::::::::
defint a-z
function checkKey% ( keyToCheck as long ) static
checkKey% = keyTable( keyToCheck \ 16& ) and PowerOf2( keyToCheck and 15& )
end function
'' :::::::::
'' name: loadKeyTable
'' desc: Loads a bunch of valid keys
'' note: This is to be run BEFORE starting to time
''
'' :::::::::
defint a-z
sub loadKeyTable ( filename as string ) static
dim currKey as long
dim keysRead as long
dim keysInFile as long
dim i as integer, j as integer
dim indxa as integer, indxb as integer
for i = 0 to 14
PowerOf2( i ) = 2^i
next i
PowerOf2( i ) = &h8000
open filename for input as #1
''
'' Clear table and load keys
''
for i = 0 to KEYMAX \ 16&
keyTable( i ) = 0
next i
while ( not eof( 1 ) )
input #1, currKey
if ( (currKey < KEYMIN) or (currKey > KEYMAX) ) then
print "Error: Invalid key in file..."
end
end if
''
'' Put key in table
''
keyTable( currKey \ 16& ) = keyTable( currKey \ 16& ) or PowerOf2( currKey and 15& )
wend
close #1
end sub
oship me and i will give you lots of guurrls and beeea
|