Author Topic: Binary lookup  (Read 6284 times)

0 Members and 1 Guest are viewing this topic.

bastya_elvtars

• Forum God
• Posts: 3 745
• Karma: +173/-7
• The rock n' roll doctor
Binary lookup
« on: 03 January, 2007, 18:01:55 »
Hello,
I'd like to make my own binary lookup implementation and would like to get some hints. Right now I will read this and post my progress.
I expect help specifically from chill. ;-)
Everything could have been anything else and it would have just as much meaning.

PtokaX forum

Binary lookup
« on: 03 January, 2007, 18:01:55 »

bastya_elvtars

• Forum God
• Posts: 3 745
• Karma: +173/-7
• The rock n' roll doctor
Re: Binary lookup
« Reply #1 on: 03 January, 2007, 21:27:21 »
Code: [Select]
`-- binary lookup routine-- bastya_elvtars, 2007-01-03-- some inspiration from CHILLCODE? production GeoIP Engine-- We create an array of numbers.arr={}x=os.clock()-- We look for a number between 2 others.sval,eval=1,1000000000000000000000000000-- the number we are looking for.requirednumber=965-- Some basic error check.if requirednumber < sval or requirednumber > eval then error("required number out of range") end-- This is basically a comparison.function chknumber (midval)  if requirednumber == midval then return 0  elseif requirednumber < midval then return 1  elseif requirednumber > midval then return 2  endendfunction lookup()  -- start and finish dynamically get redeclared.  local start,finish,retval=sval,eval,nil  -- Scope of midval should be here, so it won't get nil when  -- re-entering the while loop below.  local midval  -- If chknumber() returns 0, then the number is found!  while retval~=0 do    midval=math.floor((start+finish)/2)    retval=chknumber(midval)    if retval == 1 then -- The required number < middle value      print("required number between",start,finish)      -- As such, we lower the finish value, it is the middle value.      finish=midval    elseif retval== 2 then -- The required number > middle value      print("required number between",start,finish)      -- We raise the start to the middle value.      start=midval    end  end  print("showing time wasted: "..(os.clock()-x).."secs")endlookup()`
Any opinions?
Everything could have been anything else and it would have just as much meaning.

CrazyGuy

• Viking
• Posts: 506
• Karma: +83/-20
Re: Binary lookup
« Reply #2 on: 03 January, 2007, 23:41:05 »
ermm, what does it exactly do other then looking for a predefined number in a predefined range ?
and what's the use ?  :-\

bastya_elvtars

• Forum God
• Posts: 3 745
• Karma: +173/-7
• The rock n' roll doctor
Re: Binary lookup
« Reply #3 on: 04 January, 2007, 00:28:15 »
http://lua-users.org/wiki/TableExtension

Yeah, thanks, although I have already written my own and I learnt more that way.
Everything could have been anything else and it would have just as much meaning.

bastya_elvtars

• Forum God
• Posts: 3 745
• Karma: +173/-7
• The rock n' roll doctor
Re: Binary lookup
« Reply #4 on: 08 January, 2007, 01:05:11 »
ok, looks like I cannot get along this:
I've gotta do the following: I have 3 numbers: a,b, and c. I have to do the following:
xor(and(a,c),and(b,c))
b and c are static numbers, I have to find the smallest a value that makes the above bitwise operation's result 0. I need this for IP-range support. Can anone point me to the right direction?
Everything could have been anything else and it would have just as much meaning.

Herodes

• Guest
Re: Binary lookup
« Reply #5 on: 08 January, 2007, 07:54:30 »
Sure,... there is a pure Lua library for this ...

http://luaforge.net/projects/bit/

bastya_elvtars

• Forum God
• Posts: 3 745
• Karma: +173/-7
• The rock n' roll doctor
Re: Binary lookup
« Reply #6 on: 08 January, 2007, 12:16:41 »
Sure,... there is a pure Lua library for this ...

http://luaforge.net/projects/bit/

Yes, and I use it (even hacked it), there is no problem with that, the lookup part is what I am asking about.
Everything could have been anything else and it would have just as much meaning.

CrazyGuy

• Viking
• Posts: 506
• Karma: +83/-20
Re: Binary lookup
« Reply #7 on: 08 January, 2007, 15:32:31 »
what are the values of b and c ?

bastya_elvtars

• Forum God
• Posts: 3 745
• Karma: +173/-7
• The rock n' roll doctor
Re: Binary lookup
« Reply #8 on: 08 January, 2007, 15:57:36 »
what are the values of b and c ?

Depends. They are 3232235820 and 4294967232 now, respectively.
Everything could have been anything else and it would have just as much meaning.

CrazyGuy

• Viking
• Posts: 506
• Karma: +83/-20
Re: Binary lookup
« Reply #9 on: 08 January, 2007, 21:36:09 »
hmm, been trying to do some calculations with those numbers but it kinda screws up somewhere

By principle though, if you want the xor to result in a 0, then the results of and(a,c) and and(b,c) must match

Value 1        Value 2        Xor
1                 1             0
1                 0             1
0                 1             1
0                 0             0

Does that help anywhere ?

bastya_elvtars

• Forum God
• Posts: 3 745
• Karma: +173/-7
• The rock n' roll doctor
Re: Binary lookup
« Reply #10 on: 08 January, 2007, 22:39:02 »
No, I am over that part, thanks. BTW to show you what I am about, see this and this.
While we are at it, one use for the binary lookup is to check whether a number is in a particular (sorted) array without looping through the array. I tried that one, and it is soooo fast. :-)
Everything could have been anything else and it would have just as much meaning.

CHILLCODE?

• Scripter
• Member
• Posts: 31
• Karma: +21/-0
Re: Binary lookup
« Reply #11 on: 09 January, 2007, 00:42:30 »
okey you made the binary function yourself, and you learned a lot that way anyways, but I still wanted to to help so I tried a few things, but all this bitwise is a bit back but it seems to me the smallest a value is actualy the AND(b,c) just a little exsample, dunno if it's right

Code: [Select]
`b:11100101 -bavaluec:10101001 -cvalue&  10100001 -Andresultnow the only value to set 'Andresult' Zero through XOR: is 10100001we can be quite sure that AND'ing that with C or also B would actually return Andresult again,since it was the result of an And operationso a = AND(b,c)but I think i missed the point I guess`
furthermore are you trying to maybe do a binary search on CIDR ranges, that sounds quite interesting...
I think I also thaught once of that but have never come up with a good idea.

bastya_elvtars

• Forum God
• Posts: 3 745
• Karma: +173/-7
• The rock n' roll doctor
Re: Binary lookup
« Reply #12 on: 09 January, 2007, 01:28:10 »
Thanks for help, I will look at this tomorrow - and don't worry, I will publish the work when it is done.
Everything could have been anything else and it would have just as much meaning.

CrazyGuy

• Viking
• Posts: 506
• Karma: +83/-20
Re: Binary lookup
« Reply #13 on: 09 January, 2007, 17:18:05 »
okey you made the binary function yourself, and you learned a lot that way anyways, but I still wanted to to help so I tried a few things, but all this bitwise is a bit back but it seems to me the smallest a value is actualy the AND(b,c) just a little exsample, dunno if it's right

Code: [Select]
`b:11100101 -bavaluec:10101001 -cvalue&  10100001 -Andresultnow the only value to set 'Andresult' Zero through XOR: is 10100001we can be quite sure that AND'ing that with C or also B would actually return Andresult again,since it was the result of an And operationso a = AND(b,c)but I think i missed the point I guess`
furthermore are you trying to maybe do a binary search on CIDR ranges, that sounds quite interesting...
I think I also thaught once of that but have never come up with a good idea.

yes, thats basically what I meant as well although
a = AND(b,c)  does not seem to be right if the equation xor(and(a,c),and(b,c)) must result in a bitwise zero

AND(a,c) = AND(b,c) is what you mean right ?

CHILLCODE?

• Scripter
• Member
• Posts: 31
• Karma: +21/-0
Re: Binary lookup
« Reply #14 on: 09 January, 2007, 21:14:21 »
yes, thats basically what I meant as well although
a = AND(b,c)  does not seem to be right if the equation xor(and(a,c),and(b,c)) must result in a bitwise zero

AND(a,c) = AND(b,c) is what you mean right ?

yup to get zero  AND(a,c) = AND(b,c) is a must or?
but the smallest value for a in this case is AND(b,c)  I think,
what makes sorta no sense, why look for a variable that you already have
and then set it XOR, that's why I think I missed something.

bastya_elvtars

• Forum God
• Posts: 3 745
• Karma: +173/-7
• The rock n' roll doctor
Re: Binary lookup
« Reply #15 on: 09 January, 2007, 21:51:44 »
Umm, thanks for pointing this out, I have been waaaaaaaaaaaaay too lazy lately. I will then look into this from that point of view, especially because the extra function call introduces some overhead.
Everything could have been anything else and it would have just as much meaning.

bastya_elvtars

• Forum God
• Posts: 3 745
• Karma: +173/-7
• The rock n' roll doctor
Re: Binary lookup
« Reply #16 on: 10 January, 2007, 03:32:54 »
I think I found it out. Needs a little hack, because the bit library only accepts integer values, and therefore math.floor can lead to inaccuracies, but it actually works. Here it goes:

Code: [Select]
`--[[netmask calculation routine for RangeFuckerDoes many things:- gets a range from netmask, cidr- converts IPs to and from binary/decimal/dotted formatsReferences:http://library.thinkquest.org/28289/subnet.htmlhttp://www.ipprimer.com/bitbybit.cfmUses the LuaBit library by Han Zhao: http://luaforge.net/projects/bit/To load LuaBit library: edit package.path accordingly.Thanks to chill and CrazyGuy for hints.bastya_elvtars]]module("netmask",package.seeall)package.path="I:/luabit/?.lua"require "bit"function iptodecbin(ip)  local err  local c=256^3 local decip=0  for b in string.gfind(ip,"(%d+)") do    local piece=tonumber(b)    if not piece or piece > 255 then      err=true      break    else      decip=decip+(piece*c)      c=c/256    end  end  if not err then    return decip,bit.tobits(decip)  endendfunction DecToIP(ip)  local tmp  local pt1,pt2,pt3,pt4  pt1=math.modf((ip)/256^3)  tmp=math.fmod((ip),256^3)  pt2=math.modf((tmp)/256^2)  tmp=math.fmod(tmp,256^2)  pt3=math.modf((tmp)/256)  pt4=math.fmod(tmp,256)  return pt1.."."..pt2.."."..pt3.."."..pt4endfunction CalcMaskFromCIDR(CIDR)  if CIDR < 33 then    local bittbl={}    local counter=0    for k=1,32 do      if counter == 32 then break end -- we reached 32 bits      counter=counter+1      if counter <= CIDR then        table.insert(bittbl,1)      else        table.insert(bittbl,1,0)      end    end    if #bittbl==32 then return bittbl end  endend function GetRange(decip,decmask)  local start,en=0,decip  local mid=math.floor((start+en)/2)  local x=os.clock()  while ret~=0 do    if en==start+1 then break end    mid=math.floor((start+en)/2)    if bit.band(mid,decmask)==bit.band(decip,decmask) then      en=mid    else      start=mid    end    print(start,mid,en)  end  print(os.clock()-x.." secs wasted")  if bit.band(mid,decmask)~=bit.band(decip,decmask) then mid=mid+1 end  decip1=mid  start,en=decip,2^32-1  local mid=math.floor((start+en)/2)  local x=os.clock()  while ret~=0 do    if en==start+1 then break end    mid=math.floor((start+en)/2)    if bit.band(mid,decmask)==bit.band(decip,decmask) then      start=mid    else      en=mid    end    print(start,mid,en)  end  if bit.band(mid-1,decmask)==bit.band(decip,decmask) then mid=mid-1 end  decip2=mid  print (DecToIP(decip1),DecToIP(decip2))  return DecToIP(decip1),DecToIP(decip2)enda=iptodecbin("160.114.118.255")b=iptodecbin("255.255.255.0")print(GetRange(a,b))[/quote]`
Everything could have been anything else and it would have just as much meaning.

PtokaX forum

Re: Binary lookup
« Reply #16 on: 10 January, 2007, 03:32:54 »