flat assembler
Message board for the users of flat assembler.

flat assembler > Macroinstructions > [fasmg] Lucas Prime Test

Author
Thread Post new topic Reply to topic
bitRAKE



Joined: 21 Jul 2003
Posts: 2673
Location: dank orb
Code:
; Lucas Prime Test

; fails for composites: http://oeis.org/A005845
;  705, 2465, 2737, 3745, 4181, 5777, 6721, ...
MACRO LucasCheck num
  LOCAL l0,l1,Lucas
  l0 = -1
  l1 = 2
  REPEAT num
    Lucas = l0 + l1
    l0 = l1
    l1 = Lucas
  END REPEAT
  IF (Lucas-1) MOD num = 0
    DISPLAY `num,": Lucas pseudoprime",13,10
  ELSE
    DISPLAY `num,": Composite Number",13,10
  END IF
END MACRO

LucasCheck 705
LucasCheck 1973
LucasCheck ((1 SHL 19) - 19) ; about ten seconds    
Rereading the manual - so many new features to play with. So far my favorite is continue/file of VIRTUAL - powerful!

Start with some numbers, though.

_________________
unlicense.org
Post 23 Apr 2018, 22:54
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2673
Location: dank orb
Next I try to verify some data: There is list of cube sums at https://arxiv.org/abs/1604.07746v1

Seemed rather simple at first, but how to do it without altering the file?
Code:
VIRTUAL AT 0
  BLOCK::
END VIRTUAL

POSTPONE
  VIRTUAL BLOCK
    LOAD data:$@-$$ from $$
  END VIRTUAL
  EVAL data
END POSTPONE

MACRO DisplayNumber in
  LOCAL number
  number = in scale 0
    IF number < 0
      DISPLAY '-'
      number = -number
    END IF
    REPEAT 1, n:number
      DISPLAY `n
    END REPEAT
END MACRO

VIRTUAL BLOCK
  MACRO ?! line&
    MATCH =END =VIRTUAL,line
      END VIRTUAL
      PURGE ?
    ELSE MATCH =INCLUDE txt,line
      file txt
      db 10
    ELSE
      db `line,10
    END MATCH
  END MACRO

  results = 0
  MACRO ?! line&
    MATCH =EOF,line
      PURGE ?
      DISPLAY 10,"Found "
      DisplayNumber results
      DISPLAY " known cube sums.",10,10
    ELSE MATCH k= x= y= z= q,line
      ; assume header
      DISPLAY "Unknown line: ",`line,10
    ELSE MATCH k= x= y= z,line
      IF ~ defined k
        DISPLAY "Unknown line: ",`line,10
      ELSE IF k = (x)*(x)*(x) + (y)*(y)*(y) + (z)*(z)*(z)
        results = results+1
      ELSE
        DISPLAY "Unknown line: ",`line,10
       END IF
    ELSE
      DISPLAY "Unknown line: ",`line,10
    END MATCH
  END MACRO
  INCLUDE "sumofthreecubes_20160426.txt"
  EOF
END VIRTUAL    
Minimal error checking to bypass the header. Result matches what the paper says. This way I get to use FASMG to parse the lines, but I always wonder if there is an easier way?
Code:
flat assembler  version g.i4pue
Unknown line: List of solutions of x^3 + y^3 + z^3 = k for k < 1000
Unknown line: k not s^3 or 2*s^3 (s integer)
Unknown line: x, y, and z bounded up to 10^15
Unknown line: Sander G. Huisman 26-04-2016
Unknown line: Results combined with previous results.
Unknown line: ------------------------------------------------
Unknown line: k x y z
Unknown line: ------------------------------------------------

Found 15254 known cube sums.


2 passes, 0.7 seconds, 0 bytes.    

_________________
unlicense.org
Post 24 Apr 2018, 04:59
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 7007
Location: Kraków, Poland
I'm glad to see someone else having fun with it! Wink

bitRAKE wrote:
This way I get to use FASMG to parse the lines, but I always wonder if there is an easier way?
If the file you want to parse may contain absolutely everything, then there may be no easier way. [EDIT] Then I found an easier way, see below. [/EDIT]
But you could make these headers help instead of just being obstacles:
Code:
MACRO DisplayNumber in
  LOCAL number 
  number = in scale 0 
    IF number < 0 
      DISPLAY '-' 
      number = -number 
    END IF 
    REPEAT 1, n:number 
      DISPLAY `n 
    END REPEAT 
END MACRO

results = 0

macro List tail&
 purge List
 macro ?! line&
    MATCH =EOF,line
      PURGE ? 
      DISPLAY 10,"Found " 
      DisplayNumber results 
      DISPLAY " known cube sums.",10,10 
    ELSE MATCH k= x= y= z= q,line 
      ; assume header 
      DISPLAY "Unknown line: ",`line,10 
    ELSE MATCH k= x= y= z,line 
      IF ~ defined k 
        DISPLAY "Unknown line: ",`line,10 
      ELSE IF k = (x)*(x)*(x) + (y)*(y)*(y) + (z)*(z)*(z) 
        results = results+1 
      ELSE 
        DISPLAY "Unknown line: ",`line,10 
       END IF 
    ELSE 
      DISPLAY "Unknown line: ",`line,10 
    END MATCH 
 end macro
end macro

INCLUDE "sumofthreecubes_20160426.txt"
EOF    
And another small trick to get rid of EOF macro:
Code:
MACRO DisplayNumber in
  LOCAL number 
  number = in scale 0 
    IF number < 0 
      DISPLAY '-' 
      number = -number 
    END IF 
    REPEAT 1, n:number 
      DISPLAY `n 
    END REPEAT 
END MACRO

results = 0

macro List tail&
 purge List
 local File
 File := __FILE__
 macro ?! line&
    if __FILE__ <> File
      PURGE ? 
      DISPLAY 10,"Found " 
      DisplayNumber results 
      DISPLAY " known cube sums.",10,10
      line
    ELSE MATCH k= x= y= z= q,line 
      ; assume header 
      DISPLAY "Unknown line: ",`line,10 
    ELSE MATCH k= x= y= z,line 
      IF ~ defined k 
        DISPLAY "Unknown line: ",`line,10 
      ELSE IF k = (x)*(x)*(x) + (y)*(y)*(y) + (z)*(z)*(z) 
        results = results+1 
      ELSE 
        DISPLAY "Unknown line: ",`line,10 
       END IF 
    ELSE 
      DISPLAY "Unknown line: ",`line,10 
    END MATCH 
 end macro
end macro

INCLUDE "sumofthreecubes_20160426.txt"    


Also, to make it a bit more universal, instead of "macro Line" you could use "macro ?" and then count on the first line of included file to not contain any unconditional directive/macro. INCLUDE is an unconditional instruction (so "macro ?" does not catch it) because it has an unconditional variant (the one when "!" modifier is used).


Last edited by Tomasz Grysztar on 25 Apr 2018, 14:17; edited 1 time in total
Post 25 Apr 2018, 11:05
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 7007
Location: Kraków, Poland
On a second thought, you could use that trick which allows to switch to namespace than contains no defined instructions and then "macro ?" should catch the first line of included file universally:
Code:
MACRO DisplayNumber in 
  LOCAL number  
  number = in scale 0  
    IF number < 0  
      DISPLAY '-'  
      number = -number  
    END IF  
    REPEAT 1, n:number  
      DISPLAY `n  
    END REPEAT  
END MACRO 

results = 0 

macro ProcessLine line& 
  MATCH k= x= y= z= q,line 
    ; assume header 
    DISPLAY "Unknown line: ",`line,10 
  ELSE MATCH k= x= y= z,line 
    IF defined k & k = (x)*(x)*(x) + (y)*(y)*(y) + (z)*(z)*(z) 
      results = results+1 
    ELSE 
      DISPLAY "Unknown line: ",`line,10 
    END IF 
  ELSE 
    DISPLAY "Unknown line: ",`line,10 
  END MATCH 
end macro 

macro Finish 
  DISPLAY 10,"Found " 
  DisplayNumber results 
  DISPLAY " known cube sums.",10,10 
end macro 

macro _ProcessFile path, MACRO, END, INCLUDE

  local space 

  NAMESPACE space     ; enter a namespace with no instructions 

  MACRO ? first_line&
   END NAMESPACE
   purge ?
   _FILE := __FILE__
   macro ?! line&
     if __FILE__ = _FILE
       ProcessLine line
     else
       purge ?
       Finish
       line
     end if
   end macro
   first_line
  END MACRO

  INCLUDE path

end macro 

macro ProcessFile path
  _ProcessFile path, macro, end, include
end macro 

ProcessFile "sumofthreecubes_20160426.txt"    
Post 25 Apr 2018, 11:46
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2673
Location: dank orb
Very fast solution to unique digit sequences:
Code:
struc NextKBitNumber
  local smallest,ripple
  smallest = . and (- .)
  ripple = . + smallest
  . = ripple or ((. xor ripple) shr (2 + (bsf smallest)))
end struc

repeat 9
  ; number of digits = bits set
  n = (1 shl %) - 1
  while (bsr n) < 9
    repeat 9
      m = n and (1 shl (%-1))
      if m
        display "0"+%
      end if
    end repeat
    display 13,10
    n NextKBitNumber
  end while
end repeat    
I intentionally skipped the zero digit: it makes the output much longer and creates another test in the inner loop. Not a big deal.

References:
http://beust.com/weblog/2008/08/28/coding-challenge-wrap-up/
http://realtimecollisiondetection.net/blog/?p=78

BSF instruction is a significant reduction.

_________________
unlicense.org
Post 09 May 2018, 05:20
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2018, Tomasz Grysztar.

Powered by rwasa.