Page 1 of 1

MOD speed

Posted: Sat Jun 23, 2018 10:24 pm
by tsh73
Hello all
(a bit of long story)
Recently there was a task posted at LB forum
http://libertybasiccom.proboards.com/th ... -task-fast
Basically, it lead me to writing a program with long calculation involving MOD
I made some assumptions as to how to reduce search, and got right answer. (equal to with Rosetta code one)
After some thinking I got that idea that my seems-so-clever approach is not actually so:
I got number but I can't be sure that I checked all other numbers!
So I run it overnight, with single big loop (987654321, that much)
In the morning I discovered some error (like Virtual machine stack overflow)
and timestamp, so it run for 6 hours then crashed.
No other reason given.

(btw I recoded same program in Python - that is basic literally translated to Python, just after reading some first chapters in Python, yes - and it run overnight without no error.
But netbook I run it on fall asleep as I leaved it - so in the morning it finished but gave me total time 11 hours. I really think actual time was about 2 hours)

Anyway.
So I ran it on LBB and went away.
In the evening I saw program finished, right answer found, but total time is 9 hours!
I really expect LBB run faster - or my previous estimate for LB (6 hours) is grossly incorrect (as well could be).
Because - well - it's just FOR, WHILE, IF - nothing LB-specific? - should run much faster.
So I asked LBB to Options/show LBB pane
Whoa!

Code: Select all

if j mod 100000=0 then print ".";
turned to

Code: Select all

IF FN_mod(j, 100000) = 0 THEN PRINT FN_crlf(".");
So every MOD turned to function call
(btw that means getting rid of these dots would sped up my code a lot)

So I went searching
Here's help for BBC basic MOD
http://www.bbcbasic.co.uk/bbcwin/manual/bbcwin6.html
Indeed it works just for integers
LB does some extra stuff, emulating that requires a function
But the point is - just here I do not need extra stuff and would be happy with integer MOD!

So I tried using BBC code via "!"
something like

Code: Select all

!res=a mod b
But LBB keep saying "Mistake at line "##, pointing to that line.

Help at
http://lbbooster.com/lbb.html
on "! BBC code" says
If a line starts with an exclamation mark (!) the rest of the line is assumed to consist of BBC BASIC code and is passed, unmodified, to the output of the translator. This facility should be used with care since only a subset of BBC BASIC statements may be safely used.
So either assignment is not in this subset (that would really be a pity) or I am doing something wrong
(or rather doesn't know right "spell").

Ok so I went reading Help further.
%mode std
This directive causes LBB to evaluate the INT() function, and expressions containing both AND and OR operators, in a standard way; note that there must not be a space after the percent sign. Specifically the INT function truncates towards minus infinity (e.g. INT(−3.5) is −4) and OR has a lower precedence than AND (e.g. 1 OR 2 AND 4 is 1).
Interesting one.
Difference between workings of INT - may be there is same for difference in MOD?
LBB pane shows that by default, INT() changes to FN_int()
but with "%mode std" directive it just stays INT(), that is, native BBC Basic.
Should be faster?
Let's see how much faster it goes
This code tries to check how much loops fits in a second

Code: Select all

'%mode std
N =1
tTreshold=1000
b=5
x=123
do
    t0=time$("ms")
    for i = 1 to N
        a=int(x/b)
    next
    t1=time$("ms")
    dt=t1-t0
    N=N*1.1
loop until dt > tTreshold
print N 
(on my machine)
this first line commented
290960.772
this first line uncommented (native INT)
686070.281
Indeed, faster.
But alas "%mode std" does not affects MOD.

BUT
instead "x MOD b " I can use "x - b*INT(x/b)"
Let's compare using same program
"res = X MOD b "
290960.772
"res = x - b*INT(x/b)" , "%mode std" off
264509.793
"res = X - b*INT(X/b)" , "%mode std" on (native INT)
515454.757

so still I can make it run 75% faster ;)

Now I'll go and change my long-running program...

Re: MOD speed

Posted: Wed Jun 27, 2018 2:26 am
by JackKelly
Hi Anatoly. Good to talk to you again. Thanks for bringing this topic over to LBB. I hope John won't be too upset. But it got me thinking, and back to coding, which is always good.

I putzed around with tests of the MOD method and the INT method and didn't see any significant differences between them on my HP laptop. I saw bigger differences between the long runs that I assume were due to Windows 10 background stuff going on.

As far as solving the Rosetta Code problem, an efficient solution comes from logic, not from code. The largest integer cannot be more than nine digits long. Ten or more digits would have to have zeros or duplicate digits. The largest nine digit candidate is 987654321. So make this the starting number and count DOWN from there! The first hit is the answer.

Here's my brute-force (un-elegant) code, which finds the answer instantly.

print "What is the largest integer that contains all different, non-zero digits;"
print "and such that each digit is evenly divisible into the integer?"
print
n=987654322
[Start]
let n=n-1
n$=str$(n)
dim DigitCount(9)
Good=1
for DigitNumber=1 to len(n$)
    Digit=val(mid$(n$,DigitNumber,1))
    if Digit=0 then Good=0: exit for
    DigitCount(Digit)+=1
    if DigitCount(Digit)>1 then Good=0: exit for
next DigitNumber
if not(Good) then goto [Start]
for DigitNumber=1 to len(n$)
    if n mod Digit <> 0 then Good=0: exit for
next DigitNumber
if Good then
    print "The answer is "; n
    print "Program Completed."
    end
else
    goto [Start]
end if

Re: MOD speed

Posted: Wed Jun 27, 2018 9:52 pm
by tsh73
Jack,
you program instantly (!) said
What is the largest integer that contains all different, non-zero digits;
and such that each digit is evenly divisible into the integer?

The answer is 987654312
Program Completed.
Now 987654312 surely not divisible by 5
so there are some errors in a program.

As a side note, "987654321" is awful lot.
Rosetta code says actual answer is 7-digit, so to get it, you should pick almost all of it
Even enumerating one million numbers (in a FOR or like in your program) requires about 1 second
So expect around 1000 seconds just to enumerate numbers.
-- so "instantly" seems not plausible.

Re: MOD speed

Posted: Thu Jun 28, 2018 5:16 pm
by JackKelly
You are completely correct, Anatoly, as always! My code had a bug, AND the idea of counting down from the largest possible integer is ridiculous. My revised code counts up from 1, and finds the largest seven digit answer in about three minutes. It can examine all the eight-digit integers (up to 99,999,999) in about 20 minutes. But how can one be CERTAIN that no nine-digit integer will meet the criteria? However, it takes too long to examine all of them.

Here's my code, so far:

- - - - - - - - - - - - - - -
print "What is the largest integer that contains all different, non-zero digits;"
print "and such that each digit is evenly divisible into the integer?"
print
'The correct answer is 9,867,312
Tstart=time$("seconds")
[Start]
if n=987654321 then
Tend=time$("seconds")
if Tstart>Tend then Tend=Tend+(12*3600)
call PrintHMS Tend-Tstart
print "The answer is "; N
print "Program Completed."
end
end if
n+=1
n$=str$(n)
dim DigitCount(9)
Good=1
for DigitNumber=1 to len(n$)
Digit=val(mid$(n$,DigitNumber,1))
if Digit=0 then Good=0: exit for
DigitCount(Digit)+=1
if DigitCount(Digit)>1 then Good=0: exit for
next DigitNumber
if not(Good) then goto [Start]
for DigitNumber=1 to len(n$)
Digit=val(mid$(n$,DigitNumber,1))
if n mod Digit <> 0 then Good=0: exit for
next DigitNumber
if Good then
N=n
locate 10, 5
print using("#,###,###", N)
end if
goto [Start]

sub PrintHMS Seconds
Hours=int(Seconds/3600)
Minutes=int((Seconds mod 3600)/60)
Seconds=Seconds mod 60
print "Hours = "; Hours; ", Minutes = "; Minutes; ", Seconds = "; Seconds; "."
end sub
- - - - - - - - - - - -- -

Re: MOD speed

Posted: Thu Jun 28, 2018 9:29 pm
by tsh73
My code had a bug, AND the idea of counting down from the largest possible integer is ridiculous.
I still think idea is Ok. We need larges number - so first one that fits would work.
The only problem is that it happens very-very afterwards...
But how can one be CERTAIN that no nine-digit integer will meet the criteria?
Ah! You said
>> an efficient solution comes from logic, not from code
:)
see after next paragraph.
However, it takes too long to examine all of them.
I would say if you have 8-digits in 20 minutes that 9 digits should be 10x of that. That is just above 3 hours - not 40 days as one person on LB forum estimated for his task!
=====================================================
So on
But how can one be CERTAIN that no nine-digit integer will meet the criteria?
First Rosetta code solution (I believe C one) explains that there could be no more then 8 digits!
This is not my idea - and by John's conditions
DON'T read all the examples on RC- try to solve it yourself!
it is cheating
- but it is sure clever thing.

Re: MOD speed

Posted: Thu Jun 28, 2018 9:31 pm
by JackKelly
I have an idea. We don't have to test ANY 8 or 9 digit integers, because we're going to propose a new mathematical theorem which states, "No integer with more than seven unique, non-zero digits can be evenly divisible by each of its digits." This will be called the "Anatoly and Jack Postulate." Now all we have to do is prove it!

The proof has something to do with the mutual exclusivity of 4 and 5. This is based on the following observations:

* For ALL integers, NONE that satisfy the criteria contain BOTH a 4 and a 5.

* For integers four or more digits in length, none that satisfy the criteria contain a 5.

* For integers seven digits in length, none that satisfy the criteria contain EITHER a 4 or a 5.

The conclusion from these observations is that ANY eight or nine digit integer with all unique non-zero digits, MUST contain a 4 or a 5, and therefore CANNOT meet the criterion of even digit divisibity.

Therefore we need only to examine the integers from 1 to 9,999,999 to find the largest one which satisfies the three criteria -- which my program does (using LBB running on an HP Envy under Windows 10) in 1 min 50 sec, and in 9 min 12 sec using JustBASIC.

But WHY does 4 and 5 behave in such a way???

Test Program
- - - - - - - - -
n=0
[Start]
if n=9999999 then print "Program Completed.": end
n+=1
n$=str$(n)
dim DigitCount(9)
Good=1
for DigitNumber=1 to len(n$)
Digit=val(mid$(n$,DigitNumber,1))
if Digit=0 then Good=0: exit for
DigitCount(Digit)+=1
if DigitCount(Digit)>1 then Good=0: exit for
next DigitNumber
if not(Good) then goto [Start]
for DigitNumber=1 to len(n$)
Digit=val(mid$(n$,DigitNumber,1))
if n mod Digit <> 0 then Good=0: exit for
next DigitNumber
if Good then
print using("#,###,### = ", n);
dim nArray(7)
for DigitNumber=1 to len(n$)
Digit=val(mid$(n$,DigitNumber,1))
nArray(DigitNumber)=Digit
next DigitNumber
sort nArray(), 0, 7
for x=1 to 7
if nArray(x)<>0 then print nArray(x); " ";
next x
print: input x$
end if
goto [Start]

Re: MOD speed

Posted: Thu Jun 28, 2018 10:01 pm
by tsh73
So few interesting things I got from it

1) newer computer at my workplace works about 2x faster then my old home one
But different constructs differ in speed gain

2) I was coding "getting digits from a number" as

Code: Select all

nn = 987654321
while nn
        d=nn mod 10
        'print d
        nn=int(nn/10)
wend        
That explains why MOD speed makes a difference in my code
But I found that your approach

Code: Select all

nn = 987654321
n$=str$(nn)
for DigitNumber=1 to len(n$)
    Digit=val(mid$(n$,DigitNumber,1))
    'print Digit
next
actually works faster (just a bit faster) in LBB on both my computers.
(while 60% slower then mod/int solution in JB)
By using tricks (%mode std and using native INT instead of MOD) I make computing version work 80% faster then string one on faster computer.
Using some tricks on string version (asc()-48 instead of val() for getting digit value) this was reduced to just 20%

But on a slower computer, with both tricks ON string version work faster by 60%.

So one have to measure - no ready "always better" recipe :(

3. Watching LBB BBC-basic panel proves really handy if you trying to squeeze some speed.
If you see something starting with FN_ in a tight loop, you sometimes might rephrase coding so LBB uses only native BBC Basic operators.
Like MOD to INT (with %mode std)
Or, code

Code: Select all

if not(a) then
converts to

Code: Select all

IF (FN_int(a)=FALSE) THEN 
while

Code: Select all

IF a = 0 THEN
stays unchanged (=> works faster.)