Re: A binary search algorithm that searches for an element similar tothe key

Discussion in 'C Programming' started by 88888 Dihedral, Dec 21, 2011.

  1. On Wednesday, December 21, 2011 7:13:05 AM UTC+8, pozz wrote:
    > I want to write the function binsearch_low() with the same interface of
    > bsearch() standard function:
    >
    > void * binsearch_low (const void *key, const void *array, size_t count,
    > size_t size, comparison_fn_t compare);
    >
    > This function should return a pointer to the element of the array that
    > is the greatest among the element with a lower value than key. If no
    > element lower than key exists, the function should return NULL.
    >
    > For example, if I have the array { 10, 12, 17, 20, 25, 30 }, the
    > function should return NULL for key=8, 10 for key=11, 12 for key=12, 20
    > for key=22, 30 for key=33.
    >
    > I started from a bsearch() implementation...
    >
    > void *
    > binsearch_low (const void *key, const void *array, size_t count, size_t
    > size, comparison_fn_t compare)
    > {
    > int left = 0, right = count - 1;
    > while (left <= right) {
    > const int mid = (left + right) / 2;

    mid is a variable

    > void *element = (unsigned char *)array + mid * size;

    element is a pointer that stores address
    > if (compare(key, element) > 0) left = mid + 1;

    *element is of type unsigned char but element is of type void *

    > else if (compare(key, element) < 0) right = mid - 1;
    > else return (unsigned char *)array + mid * size;
    > }
    > return NULL;
    > }
    >
    > ...and arrived to the following algorithm:
    >
    > void *
    > binsearch_low (const void *key, const void *array, size_t count, size_t
    > size, comparison_fn_t compare)
    > {
    > int left = 0, right = count - 1;
    > while (left < right - 1) {
    > const int mid = (left + right) / 2;
    > void *element = (unsigned char *)array + mid * size;
    > if (compare(key, element) > 0) left = mid;
    > else if (compare(key, element) < 0) right = mid - 1;
    > else return (unsigned char *)array + mid * size;
    > }
    > if (compare(key, (unsigned char *)array + left * size) < 0) {
    > return NULL;
    > } else if (compare(key, (unsigned char *)array + right * size) >= 0) {
    > return (unsigned char *)array + right * size;
    > } else {
    > return (unsigned char *)array + left * size;
    > }
    > }
    >
    > Do you have any suggestions and/or improvements?


    kind of lousy for programs that mix a pointer declared and
    the type that a pointer points to
    88888 Dihedral, Dec 21, 2011
    #1
    1. Advertising

  2. I wrote a binary search in assembly in 386 20 years ago.

    This is trivial. There were EAX, EBX, ECX, EDX and ESI, EDI which are 6
    32 bit general registers and a stack that can be pushed and popped.

    I suggest you store the array starting address in ESI and use EDI as a general
    pointer in the heap.

    A program in C code within 20 lines should be coded in assembly easily for professionals in any 32 bit cpu easily.

    I'll warn any programmer that dare to use any lousy name of any variable
    to be a pointer witout ptr* or p* in the name under my supervision.


    Then I'll ask the programmer to convert the program into a specified assembly
    to prove the programmer is not stealing codes form others and faking to be
    his own works.
    88888 Dihedral, Dec 21, 2011
    #2
    1. Advertising

  3. Re: A binary search algorithm that searches for an element similar to the key

    88888 Dihedral <> writes:

    > I wrote a binary search in assembly in 386 20 years ago.
    >
    > This is trivial. There were EAX, EBX, ECX, EDX and ESI, EDI which are 6
    > 32 bit general registers and a stack that can be pushed and popped.
    >
    > I suggest you store the array starting address in ESI and use EDI as a
    > general pointer in the heap.
    >
    > A program in C code within 20 lines should be coded in assembly easily
    > for professionals in any 32 bit cpu easily.
    >
    > I'll warn any programmer that dare to use any lousy name of any variable
    > to be a pointer witout ptr* or p* in the name under my supervision.


    How many programmers are there under your supervision?

    > Then I'll ask the programmer to convert the program into a specified assembly
    > to prove the programmer is not stealing codes form others and faking to be
    > his own works.


    --
    Ben.
    Ben Bacarisse, Dec 21, 2011
    #3
  4. 88888 Dihedral

    Seebs Guest

    Re: A binary search algorithm that searches for an element similarto the key

    On 2011-12-21, 88888 Dihedral <> wrote:
    > A program in C code within 20 lines should be coded in assembly
    > easily for professionals in any 32 bit cpu easily.


    I'm guessing you haven't used all that many 32-bit CPUs.

    > Then I'll ask the programmer to convert the program into a specified assembly
    > to prove the programmer is not stealing codes form others and faking to be
    > his own works.


    Er, why?

    FWIW, I have only enough knowledge of various assembly languages to read
    simple stuff in them. Can't write any, never had a need to. It's not one
    of the most relevant skills these days.

    -s
    --
    Copyright 2011, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    I am not speaking for my employer, although they do rent some of my opinions.
    Seebs, Dec 21, 2011
    #4
  5. Re: A binary search algorithm that searches for an element similar to the key

    88888 Dihedral <> writes:
    [...]
    > A program in C code within 20 lines should be coded in assembly easily
    > for professionals in any 32 bit cpu easily.


    But why on Earth would anyone want to waste the time doing so?

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Will write code for food.
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Dec 21, 2011
    #5
  6. Re: A binary search algorithm that searches for an element similar to the key

    In article <>,
    Keith Thompson <> wrote:
    >88888 Dihedral <> writes:
    >[...]
    >> A program in C code within 20 lines should be coded in assembly easily
    >> for professionals in any 32 bit cpu easily.

    >
    >But why on Earth would anyone want to waste the time doing so?


    Why do you waste your time spewing your venom (posting) here?

    Really, it's the same question - same basic answer. The answer is: Because
    it makes you feel good and you have the time to waste.

    As do I.

    --
    They say compassion is a virtue, but I don't have the time!

    - David Byrne -
    Kenny McCormack, Dec 21, 2011
    #6
  7. 88888 Dihedral

    hopcode Guest

    Re: A binary search algorithm that searches for an element similarto the key

    Il 24.12.2011 16:37, io_x ha scritto:
    > "io_x"<> ha scritto nel messaggio
    > news:4ef5661d$0$1375$...
    >
    > Buon Natale e
    > Felice 2012
    >


    Frohe Weihnachten und
    glückliches neues 2012

    Cheers,

    --
    ..:mrk[hopcode]
    .:x64lab:.
    group http://groups.google.com/group/x64lab
    site http://sites.google.com/site/x64lab
    hopcode, Dec 24, 2011
    #7
  8. 88888 Dihedral

    Nathan Guest

    On Dec 24, 1:11 pm, hopcode <> wrote:
    > Il 24.12.2011 16:37, io_x ha scritto:
    >
    > > "io_x"<>  ha scritto nel messaggio
    > >news:4ef5661d$0$1375$...

    >
    > > Buon Natale e
    > > Felice 2012

    >
    > Frohe Weihnachten und
    > glückliches neues 2012
    >


    Wishing a very Merry Christmas to all and have a Happy New Year!

    Nathan.
    Nathan, Dec 24, 2011
    #8
  9. Keith Thompsonæ–¼ 2011å¹´12月22日星期四UTC+8上åˆ5時37分25秒寫é“:
    > 88888 Dihedral <> writes:
    > [...]
    > > A program in C code within 20 lines should be coded in assembly easily
    > > for professionals in any 32 bit cpu easily.

    >
    > But why on Earth would anyone want to waste the time doing so?
    >
    > --
    > Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    > Will write code for food.
    > "We must do something. This is something. Therefore, we must do this."
    > -- Antony Jay and Jonathan Lynn, "Yes Minister"


    I love those jobs that ordinary low paid programmers can't do
    that is how I got paid well. It is not the language used but just
    the difficulties and talents required to complete tough tasks
    to get the rewards must be rare.
    88888 Dihedral, Dec 27, 2011
    #9
  10. 88888 Dihedral

    Seebs Guest

    Re: A binary search algorithm that searches for an element similarto the key

    On 2011-12-27, 88888 Dihedral <> wrote:
    > I love those jobs that ordinary low paid programmers can't do
    > that is how I got paid well.


    If your code and writing is any indication, this is a terrifying concept.

    > It is not the language used but just
    > the difficulties and talents required to complete tough tasks
    > to get the rewards must be rare.


    Huh. I would much rather put the hard work into building a robust and
    maintainable design such that the skills needed to keep it running aren't
    rare.

    The goal here is not to show off, it's to do the best work possible.
    Maintainable code is better than flashy code.

    -s
    --
    Copyright 2011, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    I am not speaking for my employer, although they do rent some of my opinions.
    Seebs, Dec 27, 2011
    #10
  11. Seebsæ–¼ 2011å¹´12月28日星期三UTC+8上åˆ4時13分54秒寫é“:
    > On 2011-12-27, 88888 Dihedral <> wrote:
    > > I love those jobs that ordinary low paid programmers can't do
    > > that is how I got paid well.

    >
    > If your code and writing is any indication, this is a terrifying concept.
    >
    > > It is not the language used but just
    > > the difficulties and talents required to complete tough tasks
    > > to get the rewards must be rare.

    >
    > Huh. I would much rather put the hard work into building a robust and
    > maintainable design such that the skills needed to keep it running aren't
    > rare.
    >


    We don't have to argue about chief technical officer's views
    and chief financial officer's views.

    CTO and CFO normally think quite differently.





    > The goal here is not to show off, it's to do the best work possible.
    > Maintainable code is better than flashy code.
    >
    > -s
    > --
    > Copyright 2011, all wrongs reversed. Peter Seebach /
    > http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    > http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    > I am not speaking for my employer, although they do rent some of my opinions.
    88888 Dihedral, Dec 27, 2011
    #11
  12. Seebsæ–¼ 2011å¹´12月28日星期三UTC+8上åˆ4時13分54秒寫é“:
    > On 2011-12-27, 88888 Dihedral <> wrote:
    > > I love those jobs that ordinary low paid programmers can't do
    > > that is how I got paid well.

    >
    > If your code and writing is any indication, this is a terrifying concept.
    >
    > > It is not the language used but just
    > > the difficulties and talents required to complete tough tasks
    > > to get the rewards must be rare.

    >
    > Huh. I would much rather put the hard work into building a robust and
    > maintainable design such that the skills needed to keep it running aren't
    > rare.
    >


    To keep of the workers on a factory to chunk out profits
    for the employers is different from controlling those machinares
    and techniques to install the assembly lines.

    > The goal here is not to show off, it's to do the best work possible.
    > Maintainable code is better than flashy code.
    >


    I agree with you for the requirements of workers
    on the mass production factories.





    > -s
    > --
    > Copyright 2011, all wrongs reversed. Peter Seebach /
    > http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    > http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    > I am not speaking for my employer, although they do rent some of my opinions.
    88888 Dihedral, Dec 27, 2011
    #12
  13. 88888 Dihedral

    Seebs Guest

    Re: A binary search algorithm that searches for an element similarto the key

    On 2011-12-27, 88888 Dihedral <> wrote:
    > We don't have to argue about chief technical officer's views
    > and chief financial officer's views.


    > CTO and CFO normally think quite differently.


    This has nothing to do with anything.

    I think at this point I'm obliged to give up. You've not yet made a lucid
    comment about C that I'm aware of. You went on at some length about needing
    a "division library" for ARM, but are apparently completely unaware of how
    actual compilers for ARM handle division. You regularly advocate taking
    perfectly functional code which can be easily maintained and will work on any
    known computer, and mangling it into something harder to maintain which works
    on only some computers and isn't even demonstrably faster. You appear to have
    permanently fixated on the state of the art in compilers in the 1970s, and
    you constantly brag about being well-paid and in charge of things and how you
    want your skills to be rare.

    This is the opposite of competence.

    Good software development should not be focused on trying to show off or
    impress people, but on making software that actually works and does its job
    well.

    It should not be focused on offering vague and irrelevant platitudes, talking
    at great length about irrelevant trivia and pretending they're highly
    significant, and trying to impress everyone with how much more money you earn
    than other people. Who CARES?

    -s
    --
    Copyright 2011, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    I am not speaking for my employer, although they do rent some of my opinions.
    Seebs, Dec 27, 2011
    #13
  14. 88888 Dihedral

    Seebs Guest

    Re: A binary search algorithm that searches for an element similarto the key

    On 2011-12-27, 88888 Dihedral <> wrote:
    > Seebs??? 2011???12???28????????????UTC+8??????4???13???54????????????
    >> Huh. I would much rather put the hard work into building a robust and
    >> maintainable design such that the skills needed to keep it running aren't
    >> rare.


    > To keep of the workers on a factory to chunk out profits
    > for the employers is different from controlling those machinares
    > and techniques to install the assembly lines.


    This is again illucid.

    >> The goal here is not to show off, it's to do the best work possible.
    >> Maintainable code is better than flashy code.


    > I agree with you for the requirements of workers
    > on the mass production factories.


    This has nothing to do with workers in factories. This is how you turn
    software development from a bunch of prima donnas who don't actually do good
    work into a career worthy of some degree of respect.

    Flashy code *does not actually work better*. Fooling around with stuff like
    that is okay recreation, but if someone's paying me for software, I try to
    deliver something which does its job, not something that shows off why I'm
    an IOCCC judge.

    -s
    --
    Copyright 2011, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    I am not speaking for my employer, although they do rent some of my opinions.
    Seebs, Dec 27, 2011
    #14
  15. Re: A binary search algorithm that searches for an element similar to the key

    88888 Dihedral <> writes:
    > Keith Thompsonæ–¼ 2011å¹´12月22日星期四UTC+8上åˆ5時37分25秒寫é“:


    Are those Chinese ideographs? Be aware that most users aren't going to
    be able to read them.

    >> 88888 Dihedral <> writes:
    >> [...]
    >> > A program in C code within 20 lines should be coded in assembly easily
    >> > for professionals in any 32 bit cpu easily.

    >>
    >> But why on Earth would anyone want to waste the time doing so?

    >
    > I love those jobs that ordinary low paid programmers can't do
    > that is how I got paid well. It is not the language used but just
    > the difficulties and talents required to complete tough tasks
    > to get the rewards must be rare.


    If you're not going to answer my question, please don't post your
    ramblings as a followup to the article in which I asked it.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Will write code for food.
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Dec 27, 2011
    #15
  16. Seebsæ–¼ 2011å¹´12月28日星期三UTC+8上åˆ6時14分23秒寫é“:
    > On 2011-12-27, 88888 Dihedral <> wrote:
    > > We don't have to argue about chief technical officer's views
    > > and chief financial officer's views.

    >
    > > CTO and CFO normally think quite differently.

    >
    > This has nothing to do with anything.
    >
    > I think at this point I'm obliged to give up. You've not yet made a lucid
    > comment about C that I'm aware of. You went on at some length about needing
    > a "division library" for ARM, but are apparently completely unaware of how
    > actual compilers for ARM handle division.


    Are you kidding about Keil C-compiler that was bought by ARM ?

    You can mix assembly with C from the products of the same company in ARM7-9-10-11 and 8051.

    Because many general instructions in many CPU are actually executed by slow
    micro-codes especially in 8051 and 8052 of the 196X AB register architecture , therefore the slowest part of the instructions might need to be optimized by professionals in applications of various parameters.

    The integer division in the x86 family does improve a lot in these years.
    88888 Dihedral, Dec 27, 2011
    #16
  17. 88888 Dihedral

    Seebs Guest

    Re: A binary search algorithm that searches for an element similarto the key

    On 2011-12-27, 88888 Dihedral <> wrote:
    > Are you kidding about Keil C-compiler that was bought by ARM ?


    No. I'm not talking about it at all. There is no reference in any way to
    that.

    I am talking about the fact that there is NO NEED WHATSOEVER for a "division
    library" for ARM, because whether or not any given CPU has a divider, *the
    C compilers already take care of this*.

    > Because many general instructions in many CPU are actually executed by slow
    > micro-codes especially in 8051 and 8052


    This sounds almost meaningful, but I'm coming to think it's just word salad.

    You seem deeply obsessed with the notion that you can somehow hugely improve
    things by outsmarting compilers, but the net result is that so far as I can
    tell you're less able to produce an actual program which does a thing than
    the average second or third year CS student.

    -s
    --
    Copyright 2011, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    I am not speaking for my employer, although they do rent some of my opinions.
    Seebs, Dec 28, 2011
    #17
  18. Seebsæ–¼ 2011å¹´12月28日星期三UTC+8上åˆ8時09分12秒寫é“:
    > On 2011-12-27, 88888 Dihedral <> wrote:
    > > Are you kidding about Keil C-compiler that was bought by ARM ?

    >
    > No. I'm not talking about it at all. There is no reference in any way to
    > that.
    >
    > I am talking about the fact that there is NO NEED WHATSOEVER for a "division
    > library" for ARM, because whether or not any given CPU has a divider, *the
    > C compilers already take care of this*.
    >
    > > Because many general instructions in many CPU are actually executed by slow
    > > micro-codes especially in 8051 and 8052

    >
    > This sounds almost meaningful, but I'm coming to think it's just word salad.
    >
    > You seem deeply obsessed with the notion that you can somehow hugely improve
    > things by outsmarting compilers, but the net result is that so far as I can
    > tell you're less able to produce an actual program which does a thing than
    > the average second or third year CS student.
    >


    Could you do RSA 1024 bit encoding and decoding in arm7 without checking
    the possibilities to improve by assembly with C ?

    If you are selling compilers , then I'll post some problems
    with a specified platform for you to recommend the compiler to
    be tested here.
    88888 Dihedral, Dec 28, 2011
    #18
  19. 88888 Dihedral

    Seebs Guest

    Re: A binary search algorithm that searches for an element similarto the key

    On 2011-12-28, 88888 Dihedral <> wrote:
    > Could you do RSA 1024 bit encoding and decoding in arm7 without checking
    > the possibilities to improve by assembly with C ?


    This is a question which has nothing to do with the assertion I was
    criticizing.

    And really, this is why I'm gonna go ahead and killfile you. You are illucid.
    You can't respond to a question or assertion; you sort of wander off in a haze
    of buzzwords and unrelated assertions.

    The assertion you made was that we needed a division library for ARM because
    the chip doesn't have a divider. In fact, that doesn't mean we need a
    "division library", it just means that the compiler vendors have to do
    something behind the scenes to make division work.

    > If you are selling compilers , then I'll post some problems
    > with a specified platform for you to recommend the compiler to
    > be tested here.


    I'm not selling compilers.

    I'm not even asserting that it is in general impossible to gain a benefit from
    hand-tuning things; I'm just asserting that you seem to leap to it as a course
    of action without a moment's thought as to the costs and benefits.

    -s
    --
    Copyright 2011, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    I am not speaking for my employer, although they do rent some of my opinions.
    Seebs, Dec 28, 2011
    #19
  20. On Dec 21, 12:36 pm, 88888 Dihedral <>
    wrote:

    > I wrote a binary search in assembly in 386 20 years ago.


    oh goody.

    > This is trivial. There were EAX, EBX, ECX, EDX and ESI, EDI which are 6
    > 32 bit general registers and a stack that can be pushed and popped.


    the tricky bit is the algorithm. Once you have the algorithm why not
    code it in a HLL? A version written in C might actually run quicker
    than your 20 year old assembler code because modern CPUs aren't 386s
    and optimisers have got very good.

    But trying to talk you out of your machine code obsession is simply a
    waste of time.

    <snip>

    > A program in C code within 20 lines should be coded in assembly easily for
    > professionals in any 32 bit cpu easily.


    why bother?

    > I'll warn  any programmer that  dare to use  any lousy name of any variable
    > to be a pointer witout ptr* or p* in the name  under my  supervision.


    we would part company pretty quickly. Next thing you'll go all
    hungarian on me.

    > Then I'll ask the programmer to convert the program into a specified assembly
    > to  prove the programmer is not stealing codes form others and faking to be
    > his own works.


    this is just stupid
    Nick Keighley, Dec 28, 2011
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ahmed Moustafa
    Replies:
    0
    Views:
    764
    Ahmed Moustafa
    Nov 15, 2003
  2. Matt Winward
    Replies:
    0
    Views:
    525
    Matt Winward
    Mar 20, 2008
  3. Weng Tianxiang
    Replies:
    7
    Views:
    1,256
    Paul Uiterlinden
    Sep 11, 2009
  4. Bogdan

    Binary tree search vs Binary search

    Bogdan, Oct 18, 2010, in forum: C Programming
    Replies:
    22
    Views:
    3,029
    Michael Angelo Ravera
    Oct 21, 2010
  5. Ben Bacarisse
    Replies:
    8
    Views:
    338
    Ben Bacarisse
    Dec 22, 2011
Loading...

Share This Page