Combinator based Computer that calculates Prime Numbers

This board is to show, discuss and archive useful combinator- and logic-creations.
Smart triggering, counters and sensors, useful circuitry, switching as an art :), computers.
Please provide if possible always a blueprint of your creation.

Combinator based Computer that calculates Prime Numbers

Postby Hogdriver » Fri Aug 21, 2015 10:45 am

Hello Factorians,

i have created a very simple Computer using the new Combinators.

It's basically a Harvard Architecture with 4 registers (reg3-reg0, with reg0 being the instruction pointer), 160 Words of ROM, 80 Words of RAM and a few 7 Segment displays for IO. At the moment it runs at 2 Instructions per second but one might be able to speed it up a little bit by reducing some propagation delays.

This is the implemented instruction set:
Code: Select all
reset         reg3 = reg2 = reg1 = reg0 = 0
nop
load0 #imm    reg0 = #imm
load1 #imm    reg1 = #imm
load2 #imm    reg2 = #imm
load3 #imm    reg3 = #imm
swap01        reg0 <-> reg1
swap02        reg0 <-> reg2
swap03        reg0 <-> reg3
swap12        reg1 <-> reg2
swap13        reg1 <-> reg3
swap23        reg2 <-> reg3
add           reg1 = reg1 + reg2
sub           reg1 = reg1 - reg2
mul           reg1 = reg1 * reg2
div           reg1 = reg1 / reg2
rem           reg1 = reg1 % reg2
jz #addr      if reg1 == 0 then reg0 = #addr
jnz #addr     if reg1 != 0 then reg0 = #addr
jlz #addr     if reg1 < 0 then reg0 = #addr
jgz #addr     if reg1 > 0 then reg0 = #addr
sti #addr     RAM[#addr] = reg1
st            RAM[reg3] = reg1
ldi #addr     reg1 = RAM[#addr]
ld            reg1 = RAM[reg3]
inc           reg1 = reg1 + 1
dec           reg1 = reg1 - 1


I wrote a simple assembler in LUA that translates my programs and fills the ROM (Constant Combinators) in the game:
Code: Select all
/c local source = "
load1 3\n
sti 2\n
load1 19\n
sti 4\n
loop1:\n
ldi 2\n
sti 1001\n
load2 2\n
div\n
sti 3\n
loop2:\n
ldi 3\n
dec\n
sti 3\n
jz prime\n
inc\n
swap12\n
ldi 2\n
rem\n
jnz loop2\n
load0 notprime\n
prime:\n
ldi 4\n\n
inc\n
sti 4\n
swap13\n
ldi 2\n
st\n
sti 1000\n
notprime:\n
ldi 2\n
inc\n
inc\n
sti 2\n
load0 loop1\n
";
local instructions = {
   reset  = { a=0 },
   nop    = { a=1 },
   load0  = { a=2, args=1 },
   load1  = { a=3, args=1 },
   load2  = { a=4, args=1 },
   load3  = { a=5, args=1 },
   swap01 = { a=6 },
   swap02 = { a=7 },
   swap03 = { a=8 },
   swap12 = { a=9 },
   swap13 = { a=10 },
   swap23 = { a=11 },
   add    = { a=12 },
   sub    = { a=13 },
   mul    = { a=14 },
   div    = { a=15 },
   rem    = { a=16 },
   jz     = { a=17, args=1 },
   jnz    = { a=18, args=1 },
   jlz    = { a=19, args=1 },
   jgz    = { a=20, args=1 },
   sti    = { a=21, args=1 },
   st     = { a=22 },
   ldi    = { a=23, args=1 },
   ld     = { a=24 },
   inc    = { a=25 },
   dec    = { a=26 }
};
local code = {};
local labels = {};
function myprint(s)
   print(s);
   game.player.print(s);
end;
function assembleSource(pass)
   local currentAddr = 0;
   for line in string.gmatch(source, "[^\n]+") do
      items = {}
      for item in string.gmatch(line, "[^%s]+") do
    table.insert(items, item);
      end;
      while #items > 0 do
    local item = items[1];
    table.remove(items, 1);
    if item then
       if string.sub(item, 1, 1) == ";" then
          items = {};
          item = nil;
       end;
    end;
    if item then
       local labelEnd = string.find(item, ":");
       if labelEnd then
          local labelName = string.sub(item, 1, labelEnd-1);
          if string.len(labelName) < 1 then error("invalid label"); end;
          if pass == 1 then
        if labels[labelName] then error("duplicate label"); end;
        labels[labelName] = currentAddr;
          end;
          item = nil;
       end;
    end;
    if item then
       local instruction = instructions[item];
       if not instruction then
          error("invalid instruction: " .. item);
       end;
       local arguments = {};
       if instruction.args then
          for i=1,instruction.args,1 do
        local argument = items[1];
        if not argument then error("missing argument"); end;
        table.remove(items, 1);
        table.insert(arguments, argument);
          end;
       end;
       if pass == 2 then
          c = {};
          table.insert(c, instruction.a);
          while #arguments > 0 do
        local argument = arguments[1];
        table.remove(arguments, 1);
        if tonumber(argument) then
           table.insert(c, tonumber(argument));
        else
           if not labels[argument] then error("unknown label:" .. argument); end;
           table.insert(c, labels[argument]);
        end;
          end;
          code[currentAddr] = c;
       end;
       currentAddr = currentAddr + 1;
    end;
      end;
   end;
end;
function setResetEntity(entity, active)
   local cond = entity.get_circuit_condition(1);
   for i=1,15,1 do cond.parameters[i] = { signal={type="item"}, count=1, index=i }; end;
   if active then cond.parameters[1] = { signal={type="virtual", name="signal-red"}, count=1, index=1 }; end;
   entity.set_circuit_condition(1, cond);
end;
function setReset(reset, active)
   local entities = game.player.surface.find_entities_filtered({area={{reset.x,reset.y},{reset.x,reset.y}}, name="constant-combinator"});
   if not entities or #entities < 1 then error("no constant-combinator at " .. reset.x .. " " .. reset.y); end;
   if #entities ~= 1 then error("found more than one constant-combinator at " .. reset.x .. " " .. reset.y); end;
   for index, entity in ipairs(entities) do
      setResetEntity(entity, active);
   end;
end;
function setInstructionEntity(entity, a, b, c)
   local cond = entity.get_circuit_condition(1);
   for i=1,15,1 do cond.parameters[i] = { signal={type="item"}, count=1, index=i }; end;
   if a then cond.parameters[1] = { signal={type="virtual", name="signal-A"}, count=a, index=1 }; end;
   if b then cond.parameters[2] = { signal={type="virtual", name="signal-B"}, count=b, index=2 }; end;
   if c then cond.parameters[3] = { signal={type="virtual", name="signal-C"}, count=c, index=3 }; end;
   entity.set_circuit_condition(1, cond);
end;
function setInstruction(memory, addr, a, b, c)
   if addr >= memory.rows * memory.columns then error("invalid memory address " .. addr); end;
   local x = memory.x0 + math.floor(addr / memory.rows) * memory.xstride;
   local y = memory.y0 + math.fmod(addr, memory.rows) * memory.ystride;
   local entities = game.player.surface.find_entities_filtered({area={{x,y},{x,y}}, name="constant-combinator"});
   if not entities or #entities < 1 then error("no constant-combinator at " .. x .. " " .. y); end;
   if #entities ~= 1 then error("found more than one constant-combinator at " .. x .. " " .. y); end;
   for index, entity in ipairs(entities) do
      setInstructionEntity(entity, a, b, c);
   end;
end;
function clearMemory(memory)
   local max = memory.rows * memory.columns - 1;
   for i=0,max,1 do
      setInstruction(memory, i, 0, 0, 0);
   end;
end;
function fillMemory(memory)
   local numInstructions = 0;
   for addr, code in pairs(code) do
      local a = code[1];
      local b = code[2];
      local c = code[3];
      setInstruction(memory, addr, a, b, c);
      numInstructions = numInstructions + 1;
   end;
   return numInstructions;
end;
local RST = {
   x = -166.5,
   y = 398.5
};
local ROM = {
   x0 = -242.5,
   y0 = 422.5,
   xstride = 4,
   ystride = 1,
   rows = 20,
   columns = 8
};
setReset(RST, true);
myprint("Assembling source ...");
assembleSource(1);
assembleSource(2);
clearMemory(ROM);
local numInstructions = fillMemory(ROM);
myprint("Done. Assembled " .. numInstructions .. " instructions.");

Just open the game console and paste that code into it. It sets the reset signal before updating the ROM which has to be cleared manually afterwards. Just remove the red signal from the lower right constant combinator in the clock/reset module.

This is a simple program that calculates prime numbers:
Code: Select all
; memory map:
; @2 = number under investigation
; @3 = current divisor
; @4 = memory address for next prime number

   load1 3
   sti 2
   load1 19
   sti 4
loop1:
   ldi 2
   sti 1001
   load2 2
   div
   sti 3
loop2:
   ldi 3
   dec
   sti 3
   jz prime
   inc
   swap12
   ldi 2
   rem
   jnz loop2
   load0 notprime
prime:
   ldi 4
   inc
   sti 4
   swap13
   ldi 2
   st
   sti 1000
notprime:
   ldi 2
   inc
   inc
   sti 2
   load0 loop1

The resulting prime numbers are stored in RAM and displayed on the IO-Displays in the lower right part of the Computer. The Display to the left shows the current number under investigation and the display on the right shows the latest prime number that has been found.

And finally a picture:
http://i.imgur.com/YG2eTT9.jpg

The entire machine is pretty modular, all the modules are connected via a central bus running red and green lines. The red line holds all the "current" values like the register values and the instruction stored at the memory address inside reg0. On the other hand the green line holds all the "new" values, like the new values for all the registers that will be written into the register file during the next clock cycle. The four seven segment displays at the top directly show the current values of all the registers (reg3, reg2, reg1, reg0 from left to right), so the right display always shows the address of the next instruction. The two displays on the right however are hooked into the RAM module and can be addressed using the special addresses 1000 and 1001, there are also three constant combinators that can be used as inputs (1003-1005).

Here's the save file if anyone wants to check it out (you might need to install some mods to be able to load it, see picture):
http://i.imgur.com/CTjwrW9.png

Here are some pictures of my base:
http://i.imgur.com/8mFKBxL.jpg
http://i.imgur.com/htbRFFJ.jpg
http://i.imgur.com/0rm3Zs0.jpg
http://i.imgur.com/XXlIOEH.jpg

That's all i have for now, i'm looking forward to your feedback :)
Attachments
Computer1.zip
(28.27 MiB) Downloaded 5395 times
Hogdriver
Manual Inserter
Manual Inserter
 
Posts: 1
Joined: Mon Aug 17, 2015 11:20 am

Re: Combinator based Computer that calculates Prime Numbers

Postby Boogieman14 » Fri Aug 21, 2015 12:36 pm

Even apart from that computer (which is waaaaay over my head) that entire base is pretty impressive. I'll probably nick a few ideas from it for my future endeavours :)
I don't have OCD, I have CDO. It's the same, but with the letters in the correct order.
Boogieman14
Filter Inserter
Filter Inserter
 
Posts: 748
Joined: Sun Sep 07, 2014 12:59 pm
Location: The Netherlands

Re: Combinator based Computer that calculates Prime Numbers

Postby Lupoviridae » Fri Aug 21, 2015 1:07 pm

This is most excellent work. Both the base and computer are very impressive. What signal/wire are you using for addressing your memory? I'm guessing the ROM and RAM use the same address enable signal, in a continuous fashion? (Eg ROM is addresses 1-160, RAM is 161-240)

Personally I am most impressed by your LUA implementation, way out of my abilities.
Lupoviridae
Fast Inserter
Fast Inserter
 
Posts: 155
Joined: Mon Apr 20, 2015 6:26 pm

Re: Combinator based Computer that calculates Prime Numbers

Postby Twinsen » Fri Aug 21, 2015 6:14 pm

My life is now complete!
Twinsen
Factorio Staff
Factorio Staff
 
Posts: 569
Joined: Tue Sep 23, 2014 7:10 am
Location: Factorio HQ

Re: Combinator based Computer that calculates Prime Numbers

Postby Shekki » Thu Sep 10, 2015 3:00 pm

very very very impressive I wish I could do bases like that someday mine end ups just too messy and inefficient. Starting new base again btw. Great work!
Shekki
Inserter
Inserter
 
Posts: 30
Joined: Fri Aug 28, 2015 1:28 pm

Re: Combinator based Computer that calculates Prime Numbers

Postby jockeril » Sat Sep 12, 2015 10:04 am

Once the first examples of the new circuit network uses where posted, I was sure it was a matter of time until this will come...

Very good work sir ! you deserve the praise your getting - It's amazing to me and you base looks good and efficient too

Keep up the good work
[request] RTL support please
[suggestion] Blueprint file cabinet for sharing BP's
Hebrew Translator for FARL & EvoGUI and much more

join me on
- Twitter[@jockeril],
- Twitch.tv/jockeril,
- Youtube/jockeril (or JoCKeR-iL)
- and steam !
Image
User avatar
jockeril
Filter Inserter
Filter Inserter
 
Posts: 277
Joined: Sun Feb 08, 2015 11:04 am
Location: Haderah, Israel

Re: Combinator based Computer that calculates Prime Numbers

Postby akyuky@gmail.com » Sat Sep 12, 2015 10:41 am

Hello Can You Send Me Your Save Or 7 segment Displays please
akyuky@gmail.com
Manual Inserter
Manual Inserter
 
Posts: 3
Joined: Wed Jul 15, 2015 6:30 pm

Re: Combinator based Computer that calculates Prime Numbers

Postby indjev99 » Sat Sep 12, 2015 12:08 pm

How long did you need to make it?
indjev99
Long Handed Inserter
Long Handed Inserter
 
Posts: 76
Joined: Thu Feb 26, 2015 2:13 pm
Location: Rousse, Bulgaria

Re: Combinator based Computer that calculates Prime Numbers

Postby Twisted_Code » Sun Sep 13, 2015 8:07 pm

This is the same sort of "because I can" extreme as the wireworld computer project, although it's a little more practical since you don't have to work with binary data.
How to report bugs effectively because everyone should know this.
The game's tech tree, a visual reference guide.
User avatar
Twisted_Code
Inserter
Inserter
 
Posts: 39
Joined: Sat Jun 06, 2015 1:15 am

Re: Combinator based Computer that calculates Prime Numbers

Postby piriform » Tue Mar 15, 2016 4:42 pm

Half-way through the design of my CPU, I came across your post. Three thoughts popped into my head

a) Wow!, He did it! :shock:
b) But I wanted to be the first :( and now I'm 5 months late :lol:
c) Must. Not. Look.

Now that I'm well into finalizing design of MK 2, I'm free to congratulate you, and ask a question.

I realize that this is more of an abstract exercise, but do you think that such an entity could have use in the game?


PS Once again, congrats.
piriform
Fast Inserter
Fast Inserter
 
Posts: 117
Joined: Mon Jan 25, 2016 10:02 pm

Re: Combinator based Computer that calculates Prime Numbers

Postby Kronoz » Wed Mar 16, 2016 7:08 pm

I went out of my way and registered just to say: wow
Kronoz
Manual Inserter
Manual Inserter
 
Posts: 4
Joined: Wed Mar 16, 2016 6:28 pm

Re: Combinator based Computer that calculates Prime Numbers

Postby SalvaMX » Wed Mar 16, 2016 11:17 pm

It is impresive what people is capable to do with this kind of games.
SalvaMX
Burner Inserter
Burner Inserter
 
Posts: 13
Joined: Wed Mar 16, 2016 10:56 pm

Re: Combinator based Computer that calculates Prime Numbers

Postby Escadin » Wed Mar 23, 2016 5:01 pm

Are you telling me you're running Miller-Rabin or AKS on a 2hz cpu? How far does it get? :o
"--? How are commands compounded in a compounded compound command commanding compound composts." -defines.lua
Escadin
Fast Inserter
Fast Inserter
 
Posts: 118
Joined: Thu Mar 17, 2016 3:15 pm

Re: Combinator based Computer that calculates Prime Numbers

Postby Amegatron » Sun Jul 03, 2016 3:55 pm

I wish I could implement something similar :/ For now I can't get how does it work, I could only construct something like ROM and RAM modules by myself, and some kind of a screen also. But how to connect them together so it could calculate something ... Even loading your save does not help me ) I suppose I need to wait some kine of afflatus to make my own CPU, because I do not have any special knowledge about CPU or microprocessor systems architecture ))) But I'm a programmer :)
Amegatron
Inserter
Inserter
 
Posts: 38
Joined: Sun Mar 06, 2016 4:12 am

Re: Combinator based Computer that calculates Prime Numbers

Postby The Eriksonn » Mon Jul 04, 2016 10:02 pm

I made a computer that does the Mandelbrot set. It is quite slow but it works at least, well not anymore since 0.13 changed some stuff around deciders.
I plan on making a new computer for 0.13 because i got stuck trying to repair the old one. :| (and i got some tricks up my sleeve to help improve it :), like the same decider changes that broke the previus one)

i used 5 iterations on a 12*12 pixel screen(12 is the limit because of the 6 tile reach of substations) and it took 30 min to render :lol:

i tried 10 iterations but it didn´t look right. I think it was because i only have 3 decimal places(way too few).

the image is from 0.12

2016-06-06 - kopia.png
2016-06-06 - kopia.png (4.2 MiB) Viewed 5834 times
The Eriksonn
Fast Inserter
Fast Inserter
 
Posts: 162
Joined: Wed Jun 08, 2016 6:16 pm


Return to Combinator Creations

Who is online

Users browsing this forum: Google [Bot] and 1 guest