Author Topic: The Complexity Theory Thread  (Read 859 times)

0 Members and 1 Guest are viewing this topic.

adarqui

  • Administrator
  • Hero Member
  • *****
  • Posts: 29463
  • who run it.
  • Respect: +6927
    • View Profile
    • Email
The Complexity Theory Thread
« on: February 01, 2015, 12:25:56 am »
0
Anything related to complexity theory.

adarqui

  • Administrator
  • Hero Member
  • *****
  • Posts: 29463
  • who run it.
  • Respect: +6927
    • View Profile
    • Email
Re: The Complexity Theory Thread
« Reply #1 on: February 01, 2015, 12:26:05 am »
0
Reserved.

adarqui

  • Administrator
  • Hero Member
  • *****
  • Posts: 29463
  • who run it.
  • Respect: +6927
    • View Profile
    • Email
Re: The Complexity Theory Thread
« Reply #2 on: February 01, 2015, 12:26:11 am »
0
Quick little idea I had tonight. Some ugly code, but whatever.

The idea is simple; given any function of one variable, figure out how it "grows" as n gets larger.

I broke this up into two modules, Growth.hs and Growth/Detective.hs:

https://github.com/adarqui/Daimyo/blob/master/Haskell/src/Daimyo/Algorithm/Growth.hs

https://github.com/adarqui/Daimyo/blob/master/Haskell/src/Daimyo/Algorithm/Growth/Detective.hs

Here are some generic growth functions:

Code: [Select]
gaps'n interval = gaps [ n | n <- interval ]
gaps'n2 interval = gaps [ n*n | n <- interval ]
gaps'logn interval = gaps [ log n | n <- interval ]
gaps'log'logn interval = gaps [ log (log n) | n <- interval ]
gaps'nfac interval = gaps [ fac n | n <- interval ]
gaps'2expn interval = gaps [ 2**n | n <- interval ]

If you notice, those functions are mapped over an interval. Then, the "gaps" taken. This is simply the distance between v+1 and v; (v+1) - v .. over the interval. Gaps is simple recursive function (I just ignore the last value, for the most part it's irrelevant over a 'proper' interval):

Code: [Select]
gaps [] = []
gaps (ij:[]) = []
gaps (ij:ik:is) = (ik - ij) : gaps (ik : is)


Here is what some gaps look like:

Code: [Select]
*Daimyo Daimyo.Algorithm.Growth> gaps'n [1..10] :: [Integer]
[1,1,1,1,1,1,1,1,1]

*Daimyo Daimyo.Algorithm.Growth> gaps'n2 [1..10] :: [Integer]
[3,5,7,9,11,13,15,17,19]

*Daimyo Daimyo.Algorithm.Growth> gaps'2expn [1..10] :: [Double]
[2.0,4.0,8.0,16.0,32.0,64.0,128.0,256.0,512.0]

*Daimyo Daimyo.Algorithm.Growth> gaps'logn [1..10] :: [Double]
[0.6931471805599453,0.4054651081081645,0.2876820724517808,0.2231435513142097,0.18232155679395468,0.15415067982725827,0.13353139262452252,0.11778303565638382,0.10536051565782634]

*Daimyo Daimyo.Algorithm.Growth> gaps'log'logn [1..10] :: [Double]
[Infinity,0.46056074819836346,0.23258643236158183,0.1492507353488296,0.10731308545554868,8.253172979561718e-2,6.636955750816886e-2,5.509564009019918e-2,4.6837437071311494e-2]

*Daimyo Daimyo.Algorithm.Growth> gaps'nfac [1..10] :: [Double]
[1.0,4.0,18.0,96.0,600.0,4320.0,35280.0,322560.0,3265920.0]

*Daimyo Daimyo.Algorithm.Growth> gaps'sin [1..10] :: [Double]
[6.78264420177852e-2,-0.7681774187658145,-0.8979225033677954,-0.20212177935521025,0.6795087764642126,0.9364020969177149,0.3323716479045927,-0.5772397613816251,-0.9561395961311263]

*Daimyo Daimyo.Algorithm.Growth> gaps'cos [1..10] :: [Double]
[-0.9564491424152821,-0.5738456600533031,0.3363488757368335,0.9373058063268382,0.6765081011871397,-0.20626803230706137,-0.8994022881519181,-0.7656302280760634,7.20587328082245e-2]

So, as you can see, those all leave a significant fingerprint.

Finally, in Growth/Detective.hs, we have a function called "detect" which takes; a function and an interval. You can pass any function of one variable to it, that operates on doubles. Detect will then try to detect what growth function it best corresponds too (of the ones we've created). The computation will basically ignore multiplicative/constant factors, because the growth function's will be sorted by the sum of their gaps and the sum of the passed function's gaps. Then we take the minimum sum (the one that matches most closely).

For example, here are some tests.

Code: [Select]
tests =
    let
        interval = [10..100]
    in
        [
            detect (\x -> 3*x+100) interval,
            detect (\x -> 3*x) interval,
            detect (\x -> 3*(x*x)+100) interval,
            detect (\x -> 3*2**x) interval,
            detect (\x -> 3*(log x)+100) interval,
            detect (\x -> 3*(log (log x))+100) interval,
            detect (\x -> 3*(fac x)+100) interval,
            detect (\x -> 10+sin x) interval,
            detect (\x -> 10+cos x) interval
        ]

Notice the multiplicative/constant factors, those won't matter. So let's run 'tests' and see what the results are:

Code: [Select]
Daimyo.Algorithm.Growth.Detective> tests
[("n",180.0),("n",180.0),("n^2",19800.0),("2^n",2.535301200456459e30),("logn",4.605170185988091),("logn",0.41578672089627844),("n!",1.8665243088788818e158)]

Looks good.

This is pretty simple. Going to try and share more of the programming i'm doing in this subforum.

ps: Added sin/cos etc:

Code: [Select]
*Daimyo Daimyo.Algorithm.Growth Daimyo.Algorithm.Growth.Detective> tests
[("n",180.0),("n",180.0),("n^2",19800.0),("2^n",2.535301200456459e30),("logn",4.605170185988091),("logn",0.41578672089627844),("sin",5.6066262743570405e-14),("cos",5.240252676230739e-14)]


EDIT: TODO, use bignums. Also, add in the ability to pass a list of results (not a function) and an interval. This way, we can 'detect' growth functions by data alone. Make it Integer -> Double, not Double -> Double. or Integer -> BigNum.

pC