Post Reply 
How do I learn RPL and solve this problem with it?
09-26-2017, 10:20 PM (This post was last modified: 09-26-2017 10:21 PM by pier4r.)
Post: #40
RE: How do I learn RPL and solve this problem with it?
So still a greedy algorithm but a bit better than "compute all" Quite quick on the 50g.

Code:

\<<
    @3167 
    "resistorToApprox" DROP
    
    
    { 10 12 15 18 22 27 33 39 47 56 68 82 }  "baseResistors" DROP
    { 1. 1.2 1.5 1.8 2.2 2.7 3.3 3.9 4.7 
5.6 6.8 8.2 10. 12. 15. 18. 22. 
27. 33. 39. 47. 56. 68. 82. 100. 
120. 150. 180. 220. 270. 330. 390. 
470. 560. 680. 820. 1000. 1200. 1500. 
1800. 2200. 2700. 3300. 3900. 4700. 
5600. 6800. 8200. 10000. 12000. 15000. 
18000. 22000. 27000. 33000. 39000. 47000.
 56000. 68000. 82000. 100000. 120000. 150000.
 180000. 220000. 270000. 330000. 390000. 
470000. 560000. 680000. 820000. 1000000. 1200000. 
1500000. 1800000. 2200000. 2700000. 3300000. 3900000. 
4700000. 5600000. 6800000. 8200000. 10000000. 12000000. 
15000000. 18000000. 22000000. 27000000. 33000000. 39000000. 
47000000. 56000000. 68000000. 82000000. } "allResistors" DROP
    DUP SIZE "allResistorsNumber" DROP
    { 0.1 10 100 1000 10000 100000 1000000 } "resistorRanges" DROP
    {} "resultSerial" DROP
    {} "resultParallel" DROP
    0 "value1" DROP
    0 "value2" DROP
    {} "allResistorsListTemp" DROP
    {} "allResistorsListTemp2" DROP
    0 "inputValueTmp" DROP
    
    \->
    @input
    resistorToApprox
    
    @localVar
    baseResistors
    allResistors
    allResistorsNumber
    resistorRanges
    resultSerial
    resultParallel
    value1
    value2
    allResistorsListTemp
    allResistorsListTemp2
    inputValueTmp
    
    \<<
      \<<
        @first we build the list of all possible resistors from the base one.
    
        @for every element in the range of resistors we expand the list of available
        @resistors
        1 resistorRanges SIZE
        FOR position
          'allResistors'
          baseResistors
          resistorRanges position GET
          *
          STO+
        NEXT
        
        @now we order the resistors, although it is not strictly needed for the result
        allResistors :2:LSORT EVAL 'allResistors' STO      
        @we can also save the result as precomputed list
      \>> 
      DROP
        @not needed, we have the list precomputed now.
    
      @here we have all the resistors needed.
      
      @####
      @serial
      
      IF
        resistorToApprox 2 >
          @only in this case serial can be done
          @otherwise the value is too little.
      THEN
        1 2
        START
          allResistors
          resistorToApprox value1 - allResistorsNumber LNDUP
          \<=
            @after this operation we have on the stack a list
            @that reports all positions less than the input value.
          1 MPOS 1 LROT HEAD
            @we have the position of the largest element in the list
            @smaller than the value
            @(would be nice if the list of davidM
            @would include even those little commands so one has not to think about them)
          allResistors SWAP GET 'value1' STO 
          
          'resultSerial' value1 STO+
        NEXT
        
        @output
        resultSerial @resistors
        resultSerial LSUM @value
        DUP resistorToApprox SWAP %T @percentage
        100 SWAP - @percentage difference
        2 RND
      END
      
      @####
      @parallel
      
      "parallel"
      
      0 'value1' STO
      1 2
      START
        allResistors INV
        resistorToApprox INV value1 - allResistorsNumber LNDUP
        \<=
          @after this operation we have on the stack a list
          @that reports all positions less than the input value.
          @now since we have the invese the larger elements are smaller
          @so what we need is the first element smaller
        1 POS
          @we have the position of the largest element in the list
          @smaller than the value
        allResistors SWAP GET 'value1' STO 
        
        'resultParallel' value1 STO+
        value1 INV 'value1' STO
      NEXT
      
      @output
      resultParallel @resistors
      resultParallel INV LSUM INV 2 RND @value
      DUP resistorToApprox SWAP %T @percentage
      100 SWAP - @percentage difference
      2 RND
    \>>
  \>>


note that serial will return positive percentage difference, parallel negative ones (because the inverted value is always bigger than the given one).

Since it is greedy, I found at least some counterexample to the question "does it found always the best solution?" for example with 28, the serial solution is ok the parallel one is off.

Anyway I learned that better to proceed by increasing improvements rather than being stuck.

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: How do I learn RPL and solve this problem with it? - pier4r - 09-26-2017 10:20 PM



User(s) browsing this thread: 1 Guest(s)