Thread: The fastest machine?

  1. #1
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472

    The fastest machine?

    I was interested to hear the direction that this thread took - and thought it might merit further discussion in its own thread.

    It got down to brute force for solving certain problems computationally, and as i may *ahem* coin it.. ;-> ..deductiveCentric, versus logicCentric algorithms to do so.

    In a perfect machine code submission I believe that a perfect deductive would beat a perfect brute force. Or would it? Is it not the nature of computing that it is most suited to just crunching numbers - ie generic to the machine? Does our brain operate in a deductive manner? at the base processing level? Or is it just harnessing the sheer hardware capability?

    [EDIT] I am thinking now in terms of weather forecasting and the like - chaos based approximations, or the merging of many scenarios are employed - not just the crunching of scenarios themselves - but that is forecasting, which is not seeking a known goal- like sudoku solving or peg solitaire solving i suppose
    Last edited by rogster001; 04-10-2015 at 02:22 PM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  2. #2
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,730
    I believe in depends on how the "fastest machine" would operate.

    If it was a quantum computer, then the brute force may be both faster and surely more accurate.
    If it was a conventional computer, then the deductive would probably be less accurate, but it'd also be much, much faster.
    Devoted my life to programming...

  3. #3
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by GReaper View Post
    ...If it was a conventional computer, then the deductive would probably be less accurate, but it'd also be much, much faster.
    ...Unless there are too many branch mispredictions, so that's not a given.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,730
    Quote Originally Posted by Elysia View Post
    ...Unless there are too many branch mispredictions, so that's not a given.
    Well, of course, all algorithms have best, worse and average case complexities, and I don't think that's something the machine can predict or hope to compensate for completely.

    But even if a branch misstep took a million more cycles to complete than a normal iteration, if the brute force had a billion more iterations to complete than the deduction one, you can see which would take longer to complete.

    Unless you're joking, it which case... I don't get it.
    Devoted my life to programming...

  5. #5
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Quote Originally Posted by rogster001 View Post
    In a perfect machine code submission I believe that a perfect deductive would beat a perfect brute force. Or would it? Is it not the nature of computing that it is most suited to just crunching numbers - ie generic to the machine?
    If you can't reason with it, crush it.

    This is implied human nature. But it is also how you find the optimum solution to solve a problem. What it means is that not always you can come up with a deductive solution to a given problem. And in that case, a brute force algorithm is both a necessity and a guaranteed win.

    Some problems don't have deductive solutions. We simply don't know yet enough about them to create valid premises and syllogisms (therefore we cannot achieve verifiable solutions). Other problems may have deductive solutions, but these do not fit well in the computing paradigm (another implication in GReaper answer) or aren't optimal enough to beat a straightforward brute force solution.

    An example of a problem without a deductive solution is any currently unsolved problem, like the Travelling Salesman Problem, or the Twin Primes Conjecture. An example of solvable problems with deductive solutions that are less optimal than brute force methods is The Four Color Theorem, in which one of the deductive proofs is composed of several hundred pages of mathematical formulations. Chess endgame solutions are also notoriously easier to compute through brute force, compared to the possible deductive alternatives.

    So it is indeed possible to come up with better brute force solution to a problem known to also have deductive methods. Two major factors will dictate when this is desirable:

    - There exists a set of heuristics that remove a large portion of the test cases. Meaning, usually only problems from which heuristics can be devised are good candidates for brute force methods.
    - We aren't tasked with finding all possible solutions (or all invalid cases), but we are content with just finding a solution or a manageable set of solutions.

    Weather forecasting is one example you gave of a problem in which you really have no other option than to provide a brute force method because it is largely an unsolved problem. But, like with most scenario modelling programs, there are already some deductive algorithms that can be applied. So it's in fact an hybrid method. Likewise, it is (at least presently) rich in heuristics that will most likely always ensure a brute force method is going to always be a more desirable approach.

    Does our brain operate in a deductive manner? at the base processing level? Or is it just harnessing the sheer hardware capability?
    Honest answer? We don't know. But this is one myth I would like to see come to an end...

    Our brain is not necessarily a good computer. Probably it is a most terribly noneffective one that, once we learn more about it, we will probably also learn to accept the idea that perhaps it is time to put a rest to this nonsense that our computers should try to mimic our brain processing power.

    And I'm saying this because we have hints about our brain lack of capabilities everywhere. Can you solve complex mathematical expressions in your brain, or is it not a fact that you can only use it for small step calculations and you need the help of your visual cortex and several seconds or minutes of thinking to both perform the step and make sure you did it correctly? Likewise, can you reliably store information in your brain, or isn't it a fact that you can't and that this is precisely why some of our mental capabilities are speedy but necessarily unreliable?

    In the evolutionary history of the human brain, we are still in the last seconds of the 31st of December, if I'm allowed the gross interpretation of Car Sagan's famous allegory. To me at least -- and looking at how unreliable and slow thinkers we are -- I think we are still holding baby brains in our heads that require a whole lot more of evolution to do to catch up with the problem solving requirements of reliability and speed.

    Despite our brains, we did have to invent computers, didn't we? So why do we want to make them like our brains?
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by GReaper View Post
    Well, of course, all algorithms have best, worse and average case complexities, and I don't think that's something the machine can predict or hope to compensate for completely.

    But even if a branch misstep took a million more cycles to complete than a normal iteration, if the brute force had a billion more iterations to complete than the deduction one, you can see which would take longer to complete.

    Unless you're joking, it which case... I don't get it.
    I'm just saying, there may be some problems where there are just so many branches that causes branch mispredictions that a brute force way is just more efficient.
    I believe that this is actually the case is some more cpu insensitive algorithms, like those used in video encoding. Even though it might mean less computations with branches, they're avoided because of the penalty for a branch misprediction.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    Despite our brains, we did have to invent computers, didn't we? So why do we want to make them like our brains?
    I suggest - To help build things that can do what we can, not just what computers can
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  8. #8
    Registered User Alpo's Avatar
    Join Date
    Apr 2014
    Posts
    877
    Our brain is not necessarily a good computer. Probably it is a most terribly noneffective one that, once we learn more about it, we will probably also learn to accept the idea that perhaps it is time to put a rest to this nonsense that our computers should try to mimic our brain processing power.
    The hardware seems similar, but yeah our brains are horrible at putting all of their resources on a single task. Plus there is all the faulty logic caused by vestiges of the things that helped us all survive a long time ago.

    As far as thought goes, most people think inductively rather than deductively. This makes sense in most cases as it is the fastest way to reach a conclusion, which may have been important in life and death scenarios.

    In programming terms inductive thinking might be something like taking an element and performing some sort of "closest match" search against another collection you have memoized, then storing the results in the memoization memory. This is why people change their minds so slowly even against evidence, their past experiences are informing how they think about a thing currently.
    WndProc = (2[b] || !(2[b])) ? SufferNobly : TakeArms;

  9. #9
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Quote Originally Posted by Alpo View Post
    As far as thought goes, most people think inductively rather than deductively. This makes sense in most cases as it is the fastest way to reach a conclusion, which may have been important in life and death scenarios
    It is not about what makes sense, but what it really goes on inside our brain. And the scientific answer is: we don't know.

    And neither can we say something like "most people think inductively". Given that we all share a similar biology as members of the same species, it is a given that whatever core mechanism we share it is going to be common across all members of our species.

    But more importantly, reasoning methods (deductive, inductive, abductive, and analogic) are inference methods that live above the core physical processes that permit logic building. They are higher level abstractions and do not represent any sort of fundamental physical property of our brains.

    This is true of the human brain as is of a computer. Whatever physical mechanism our brain uses to reason, it cannot be called deductive or inductive or whatever. That physical process is a core process that allows for any of those methods to then be used on top of it. Much like the binary processing happening inside a computer allows for all manner of different abstractions to be created.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. SSH'ing from a windows machine to a linux machine
    By BinaryProgamer in forum Networking/Device Communication
    Replies: 2
    Last Post: 12-11-2014, 10:56 PM
  2. Replies: 4
    Last Post: 01-18-2008, 07:05 PM
  3. I'm looking for the fastest!
    By Yarin in forum Windows Programming
    Replies: 4
    Last Post: 11-07-2007, 03:30 PM
  4. Porting from 32 bit machine to 64 bit machine!
    By anoopks in forum C Programming
    Replies: 10
    Last Post: 02-25-2005, 08:02 PM
  5. IDEA: A Slot Machine (aka a fruit machine)
    By ygfperson in forum Contests Board
    Replies: 0
    Last Post: 08-12-2002, 11:13 PM