Ask General Programming Questions Not Worth Their Own Thread

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Ask General Programming Questions Not Worth Their Own Thread

«‹›6 »

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Off the top of my head...

Miranda, Haskell, and that entire family of languages use it as the has-type operator. The Caml/OCaml family of languages use it as a cons, if I remember correctly. Perl and Ruby use it as a namespacing operator; probably lots of others in the nuevo-dynamic-language family.have a similar use. Several versions of make use the double-colon operator to construct prerequisite-dependent rules.

And you have got to explain why you're asking this question.

# ¿ Mar 4, 2008 11:43

Adbot: ADBOT LOVES YOU

# ¿ Apr 29, 2024 05:26

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

If you're actually drawing filled rectangles, and you have a strong z-ordering, then a very simple, fast, and easy to optimize algorithm is to simply draw all of them, starting from the back and moving to the front. This is the simplest kind of fragment rendering, imposes almost no overhead when there are few overlaps, and can be implemented in very small code with no conditionals that only has to consider one rectangle at a time.

If you just want to find out which rectangles are visible, there are a few things you can do. Possibly the best is to render them as above into an off-screen buffer somewhere, each with a separate color, then check all the pixels in your buffer to determine which colors are visible. Other algorithms exist, but tend to have higher complexity in the number of objects in exchange for not being pixel-bound as the rendering approach is, and are usually only worthwhile when you have more complicated objects than rectangles.

# ¿ Mar 6, 2008 19:15

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Alan Greenspan posted:

I want to be able to handle up to 1 million rectangles.

At this many geometry elements, you're not going to be able to do much better than the offscreen drawing mechanism, and caching the result. You're far more geometry-dominated than pixel-dominated, so many of the common alternative algorithms are going to be worse than the naive algorithm. If the rectangles move around, especially if they only move by small amounts, then there may be some updateable structures that will work marginally better than the naive method, but frankly at this point you'll have the most luck with naive drawing to an offscreen buffer, and making your drawing code as small and condition-free as you can, so you can run out of cache and avoid stalling.

# ¿ Mar 6, 2008 20:09

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Incoherence posted:

I thought about that, but wouldn't that fall down when there are duplicate elements in the input set?

Well, then it's not an input set, it's an input list, and you can do it by explicitly passing around the list of remaining elements, and chopping off prefixes of it. Or just keep the list out of band, and use an input set of integers from zero to (length of list)-1, then use those as indexes into the list.

Edit: The only time you can't do this is if there isn't a strong ordering you can impose on the input, which means the input has to be nonfinite, and hence the only length that terminates is length 0, so it doesn't matter.

ShoulderDaemon fucked around with this message at 20:08 on Mar 8, 2008

# ¿ Mar 8, 2008 20:03

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Incoherence posted:

You're not solving the problem: if your input set is {0, 1, 1, 2, 3} and you want all subsets of length 3, {1, 2, 3} using the first 1 is the same as {1, 2, 3} using the second 1.

Oh. I'd assumed that if you wanted to specify an input collection with duplicates, then that meant you wanted to break order invariance for the duplicated elements, because why else would you bother to have a representation of the input that even allowed duplicates? Transforming the input to a complete integer range and never passing around big partial collections seems far more reasonable, because you don't have to worry about sorting or uniqueness or any of that mess.

If you want the same behavior as if the input collection doesn't allow duplicates, but you still want to provide duplicates of some elements for some reason, then I'd just prefilter the input collection to remove them, which we can trivially do for a max of n ln n complexity cost (I think you can do n, but it's too late at night for me to be sure). Considering the rest of the algorithm is massively more complex by sheer size of output, there's no reason at all to try to do anything clever. The trivial construction involves a size n lookup table, but that's dwarfed by everything else and it's not like we're using memory for anything but the stack anyway.

# ¿ Mar 9, 2008 10:44

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Scaevolus posted:

Is there a name for the algorithm to convert a sorted list to a balanced binary search tree (something more efficient than iterating over the list and inserting items into an AVL tree)? I think I can do it in O(n), but Knuth probably already created a better algorithm 30 years ago or something.

Uhm... a sorted array is a balanced binary tree. The top node is the index closest to the middle, which you can get in constant time as long as you know the highest index, the left subtree is all indices before it, and the right subtree is all indices after it.

# ¿ Apr 4, 2008 03:32

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Incoherence posted:

Sounds like he wants to start with a sorted array and make a balanced binary tree so that he can add more crap to it (with O(lg n) insertion instead of O(n)).

Well then O(n) is a trivially provable lower bound, because he needs one access per node in order to create the complete tree (although he could construct a lazy tree).

To build a new tree you'd just walk the old tree in preorder and build the new tree with a balanced assumption.

code:

#include <assert.h>
#include <stdlib.h>

struct bitree {
  int           value;
  struct bitree *left;
  struct bitree *right;
};

struct bitree *array_to_bitree ( const int *array, unsigned int length ) {

  if ( length == 0 )
    return NULL;

  struct bitree *root;

  root = malloc( sizeof( struct bitree ) );
  assert( root );

  root->value = array[length / 2];

  root->left  = array_to_bitree( array, length / 2 );
  root->right = array_to_bitree( array + length / 2 + 1, length - (length / 2 + 1) );

  return root;

}

(completely untested)

# ¿ Apr 4, 2008 03:45

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Scaevolus posted:

Sorry, let me try to explain better.

I don't need to modify this tree after I've created it.
By balanced binary search tree, I mean a balanced left-heavy tree, that is, the number of nodes to the right is <= the number of nodes to the left.

Basically, I want to flatten this binary tree in an array, where I know the position of the children nodes based only on the index of the parent node. In my example, I'm transforming {1,2,3,4,5,6} to {4,2,6,1,3,5}.

The question is if this process has a name I can use to refer to it easily?

No name that I'm aware of.

But again, if you already have a sorted array, then you already have such a tree available. In this case, you'd have to tweak the code I provided so that it enforces the left-heavy nature of the tree:

code:

struct bitree *array_to_bitree ( const int *array, unsigned int length ) {

  if ( length == 0 )
    return NULL;

  struct bitree *root;

  // For left-heavy balanced trees, the head is always at index:
  // 2^(dl2 - 1) + min( 2^(dl2 - 1) - 1, length - 2^dl2 )
  // Where dl2 is the discrete log base 2 of the length.
  // Simplification of the expression is left as an exercise to the reader.

  int dl2 = 0;
  for ( unsigned int templength = length; templength > 0; templength >>= 1 )
    dl2++;

  unsigned int head = (1 << (dl2 - 1))
                    + min( (1 << (dl2 - 1)) - 1, length - (1 << dl2) );

  root = malloc( sizeof( struct bitree ) );
  assert( root );

  root->value = array[head];

  root->left  = array_to_bitree( array, head );
  root->right = array_to_bitree( array + head + 1, length - (head + 1) );

  return root;

}

If you don't want to construct the pointers, then obviously you can just iterate the index discovery expression used here.

# ¿ Apr 4, 2008 05:05

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

nbv4 posted:

I have a form on a webpage that has like 50 checkboxes. I'm using a javascript function to validate the form. I'm trying to formulate an IF statement that returns true if there are more than one of those boxes checked. I'm thinking the XOR operator would be best in this situation,

OK, no. XOR will tell you the parity of your checkboxes, but it won't tell you if more than one was checked.

If the variables checkbox1, checkbox2, etc. are all either 1 or 0, then just add them together and verify that the result is exactly 1.

# ¿ Apr 5, 2008 08:29

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Bonus posted:

So how could I modify this so that it gives me an infinite sequence but doesn't just keep going along the left branch?

What you want in Haskell would be along the lines of:

code:

qstates s = s : concat [ [ (a+1,b,c), (a,b+1,c), (a,b,c+1) ] | (a,b,c) <- qstates s ]

So, by converting to explicit iterators for Python, we wind up with something like:

code:

def quantum_states( start ):
  yield start
  for state in quantum_states( start ):
    for i, x in enumerate( state ):
      l = list( state )
      l[i] += 1
      yield tuple( l )

(completely untested, because I don't like Python)

In Haskell, this code works well because the optimizer does the right thing and builds a cycle in the intermediate graph. I kind of doubt Python is going to be that smart, so you might want to build a wrapper that memoizes an appropriate window in order to avoid going linear in stack frames. Whether or not this is worth it depends largely on how expensive the continuations wind up being.

ShoulderDaemon fucked around with this message at 17:32 on Apr 7, 2008

# ¿ Apr 7, 2008 16:35

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Jam2 posted:

What's the most efficient operating system for a web server?

The most meaningful definition of "efficient" is strongly dominated by maintainence overhead, so the answer is "whatever operating system you are most familiar with and takes the least hassle to run the software you are already using."

Operating systems do have different scheduling and memory behaviour, but the differences are going to be overwhelmed by even minor hardware changes like adding RAM. Unless you are in a situation where you need extremely high runtime or will be constantly running at close to 100% load, you shouldn't care. If you are in such a situation, then the solution needs to be finely and particularly tuned to your requirements.

# ¿ Apr 8, 2008 21:05

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Jam2 posted:

We will be streaming audio to thousands of concurrent listeners 24/7. I am just wondering what will handle the load the best.

I'm thinking it's best to stick with Windows Server 2003 simply for Windows Media Services.

If you are streaming the same audio source to all those clients, then it's hugely unlikely that the scheduling and cache differences between operating systems will be observable. If there are many different sources, then the Linux scheduling and pagecache might perform better, but adding RAM to a Windows-based server would overwhelm the difference. CPU usage is going to be comparable across the board.

It sounds like Windows Server 2003 already has the software and working environment you are used to, and has tools that will work well for your case, so it's obviously the right thing to use. Any money you "saved" over a year by switching platforms would be lost in added wages for programmer and administrator time in less than a week (probably less than a day if you're anything more than a 3-man shop), and migrating would almost certainly take much longer than that.

# ¿ Apr 8, 2008 21:36

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

clockwork automaton posted:

Is there a way to check if a read in string from fscanf() contains a newline in C? I know it ignores whitespace characters which presumably includes newlines, I just am looking for a way to tell if it has encountered and ignored these characters.

This probably isn't what you want to hear, but fscanf is a really terrible lexer, and when you get to the point of caring if a newline or something is present in the input, you should really consider moving to a lexer generated by lex or some other tool.

# ¿ Apr 8, 2008 23:15

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Orlen posted:

I'm doing some Haskell coursework and I've hit a dead end.

You've got absolutely the right idea, but the types are a little subtly wrong in the last line of your code.

Let's first create a function, leftPathEnum, that only considers paths on the left.

> leftPathEnum :: BTree a -> [Path]

leftPathEnum on leafs returns a single result: the empty path.

> leftPathEnum (Leaf x) = [ [ ] ]

On interior nodes, leftPathEnum needs to take all the paths from its left child, and stick a 'L' in front of them. We use map for this.

> leftPathEnum (Node l r) = map (L

(leftPathEnum l)

Hopefully you've been introduced to map before. It takes a function, and a list, and returns the list with that function applied to every element.

In this case, the function I've provided is (L

. The (

operator is called "cons", and its type is:

(

:: a -> [a] -> [a]

It takes a single element, and a list, and prepends the element to the list. The type of (L

is:

(L

:: [Dir] -> [Dir]

It takes a list of Dirs, and prepends L to the list.

Do you think you can write a pathEnum function now, with the same technique? You'll have to call map twice, and you'll be concatenating the results of the maps with ++.

# ¿ Apr 17, 2008 17:07

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Clock Explosion posted:

So any of you who have had experience using Hugs98 or at least WinHugs, what would be a "C stack overflow"? It's different from the standard overflow, that's all I know.

Chances are you have a really big foldl somewhere that's exploding and causing a whole lot of unevaluated thunks to wind up being created all at once. Replace it with a foldr if you don't need left-associativity, or foldl' if you do.

I can't really give you much more help without seeing some code, though.

# ¿ May 3, 2008 19:51

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Can you also post your World datatype, please?

Edit: It would also be useful to know an initial World, and if you get the stack overflow on the first call to this function, or if it only happens after a lot of iterations.

# ¿ May 4, 2008 03:20

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Post a line or two of the CSV that it exports, some guess as to how many lines it spits out (hundreds/thousands/millions), and the format that you want the statistics in. Chances are this is a really trivial job that doesn't need a database, and I can replace your job with a Perl script.

# ¿ May 22, 2008 21:15

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

JoeNotCharles posted:

code:

$ ./foobar -pants
this is a test
file1
file2
$ for i in `./foobar -pants`; do echo $i; done
this
is
a
test
file1
file2
$ for i in `./foobar -pants`; do echo "$i"; done
this
is
a
test
file1
file2

This is splitting on all whitespace, and calling echo for every word.

JoeNotCharles posted:

code:

$ for i in "`./foobar -pants`"; do echo "$i"; done
this is a test
file1
file2

This isn't splitting at all, and calling echo exactly once, with the entire output of foobar.

JoeNotCharles posted:

code:

$ for i in "`./foobar -pants`"; do echo $i; done
this is a test file1 file2

This isn't splitting at all, and calling echo exactly once, with the entire output of foobar. Because the variable isn't quoted, it is split into multiple words on whitespace, which are then all passed to echo as separate arguments. Echo doesn't know how its arguments were split, so it assumes a single space.

This should work:

code:

OLDIFS="$IFS"
IFS="
"
for i in `./foobar -pants`; do echo $i; done
IFS="$OLDIFS"

# ¿ Jun 3, 2008 22:59

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

covener posted:

Using the shell builtin 'read' may be a more straightforward way to iterate over line-based output

The only gotcha with that is it opens a subshell, so you can't set environment variables within the loop and have them propagate outside it unless you jump through some extra hoops. Depending on what kind of processing he's doing inside the loop, that may or may not matter.

# ¿ Jun 4, 2008 01:43

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

You can do it without a reverse and with a single pass through the list by carrying an accumulator with the previous element's sum.

code:

(define (calc-running-sum L) (calc-running-sum-acc 0 L))

(define (calc-running-sum-acc n L)
  (if (null? L)
    '()
    (cons (+ n (car L)) (calc-running-sum-acc (+ n (car L)) (cdr L)))
  )
)

# ¿ Jun 6, 2008 19:35

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

6174 posted:

However I've got no real experience with Postscript. Is writing a filtering type program here really as simple as my mind thinks it is?

Postscript is a turing-complete programming language. You can't, in general, programatically replace some colors with others.

You could write a Postscript interpreter that parsed the document and produced a sequence of draw commands that produced the same document, but has a predictable interior structure. Then you would be able to post-filter those commands to remove colors you don't want. This may result in a massive increase in the size of the document.

Also, keep in mind that there are several different color spaces that Postscript operates in, and depending on where the bug is in your printer, you may have to handle them as well.

# ¿ Jun 13, 2008 22:34

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

schnarf posted:

Is there any way to do it that preserves the precision a bit better?

You could multiply them before shifting, then shift the result down by 32? You'll have to cast up to 64-bit integers first, I think.

# ¿ Jun 18, 2008 19:16

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Orlen posted:

Hey guys,

Is it possible to prove

P \/ ~ P

using coq?

It's obviously always true, but I can't seem to prove it using coq, I've been at it for the last half hour trying various things but I'm completely stuck, and not getting anywhere.

That's only always true in classical logic, which is a subset of what coq allows. The simplest thing is to assert Axiom classic : forall p : Prop, p \/ ~ p. somewhere and rely on that. You may also want to look at Logic.Classical_Prop or google for "excluded middle" and "intuitionist logic".

# ¿ Oct 2, 2008 16:15

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

slovach posted:

What exactly is the .bss segement? I get that it's where it stores poo poo as the program is loading, but is it gone after that or what?

I noticed it showed up in one of my programs, but doesn't seem to actually take up any physical space. Is this right?

It stores static data that should be initialized to zero. Because it's known to contain nothing but zeroes, it's not actually realized in the executeable file - the operating system allocates space for it in RAM and fills that space with zeroes on its own.

# ¿ Oct 14, 2008 01:22

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Ugg boots posted:

In C can you somehow compare two FILE * to see if they are pointing at the same file? I don't care about compatibility with symlinks or whatever, these will be two FILE * pointing to potentially one regular file on the hard drive.

Untested, but this should work. I don't know if there's a shorter way; this is just the first solution that I thought of.

code:

#include <stdbool.h>
#include <stdio.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>

bool same_file( FILE *a, FILE *b ) {

  int a_fd = fileno( a );
  int b_fd = fileno( b );

  if (a_fd == b_fd) return true;

  struct stat a_stat;
  struct stat b_stat;

  if (fstat( a_fd, &a_stat )) return false;
  if (fstat( b_fd, &b_stat )) return false;

  return (a_stat.st_dev == b_stat.st_dev) && (a_stat.st_ino == b_stat.st_ino);

}

# ¿ Oct 24, 2008 21:27

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

ZorbaTHut posted:

Time for a horrifying Lua question!

You could be leaking zombie processes, which would explain why trivial fork-and-exec tasks are failing and also why the problem immediately goes away when you kill the parent lua process.

# ¿ Oct 28, 2008 04:58

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Sexxxy Sophitia posted:

code:

printf("That means it can store %d values.\n",(pow(2,(sizeof(w)*8))));

%d wants an int parameter. Even if pow returned an int instead of a double, you can't fit the number you want in an int, by definition. Replace %d in this line with %.0f and it should work.

# ¿ Oct 30, 2008 16:35

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

You also now have a typo: frintf instead of printf.

# ¿ Oct 30, 2008 18:03

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Mr. Jive posted:

I hit a roadblock on my very first Haskell program:

You're missing a quote on line 11, right before FOR.

# ¿ Oct 31, 2008 21:35

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Nahrix posted:

(Language: C) Is there a simple way to read a char array[x] -> array[last_element], where y > 0?

I just want to read a string, starting from a given index. (eg. read "ello" from "hello"). I don't want to make a for loop for this.

If you have char buffer[] = "Hello, World!" and you want a char * to just the second word, you can use char *world = &buffer[7] or, more directly, char *world = buffer + 7.

# ¿ Nov 4, 2008 22:37

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

ZorbaTHut posted:

Here's a wacky question.

I need an algorithm for anonymous distributed reputation. Distributed reputation is tough, but I can't come up with any possible way to make it anonymous. I'm guessing it's just not possible, but I'm wondering if there's any research along those lines Any suggestions?

Collaborative signing algorithms can be applied to this in theory, I guess. The concept of anonymous reputation seems very nearly contradictory, though; what's your actual problem domain?

# ¿ Nov 8, 2008 11:21

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

ZorbaTHut posted:

I agree that, in the most obvious form of the algorithm, when everyone needs to know exactly what everyone has rated everyone else, it's impossible to hide data. That said, I don't know if it's possible to accomplish the same thing while still preserving anonymity in any sense, or what the whole shebang would look like. That's what I'm curious about.

Edit: removed some bad implementations that you really shouldn't use

There's a blind signature scheme that kind of works for this situation, but it requires slightly esoteric encryption. Assume Alice is trying to rate Bob.

Alice has a private key with functions Aencrypt, Adecrypt.
Bob has a public key with functions Bsign, Bverify. Bverify is known to the world.
Bob has some mechanism to verify the identity of Alice.
Adecrypt(Bsign(Aencrypt(data))) = Bsign(data).
Alice wants to make rating statement foo against Bob.
Alice sends Bob Aencrypt(foo).
Bob cannot read the rating, but can verify that he is talking to Alice and has never let Alice rate him before.
Bob either refuses the rating, or sends back Bsign(Aencrypt(foo)).
Alice computes Adecrypt(Bsign(Aencrypt(foo))) to get Bsign(foo), which can be published at Alice's discretion.
Anyone checking Bob's ratings does so by examining published ratings which are correctly signed by Bob.
In this system, the ratings could be "I rate Bob poorly" or Asign("I, Alice, rate Bob poorly"); the rater is free to insert identity into the ratings (which may increase their strength, depending on your reputation algorithm) or leave them anonymous.

You can use RSA for the public keys, and a blinding multiply for the private encryption. I just checked, and Schneier has a section on this in Applied Crypto, 23.12 "Blind Signatures"; if you search, you can probably find other implementations.

If you can depend on a central ratings clearinghouse there are simpler solutions. Clearinghouses can trivially mask rater data by simply executing the reputation algorithm themselves and only returning concrete results.

ShoulderDaemon fucked around with this message at 22:11 on Nov 9, 2008

# ¿ Nov 9, 2008 22:09

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

ZorbaTHut posted:

Well that's pretty dang clever. I suppose the only objection I have is that the obvious thing for Bob to say is "okay, I've signed it, now you have to reveal what it is" and, of course, 99% of people will reveal it instantly unless it's bad. Kind of an instant giveaway.

Also, if a group goes badly, everyone would probably just reject rating requests from everyone else ("ha ha can't rate me down now, sucka!")

If we admit some DRM, I think this is doable:

All messages to be tagged by some globally unique number, ideally a large random nonce.

When Alice and Bob first meet, Alice has Bob blind-sign two messages: a good rating, and a bad rating. As many times as he wants, Bob has Alice reveal both messages then discard them and repeat the exchange: this is to convince Bob that Alice is not cheating by generating two bad ratings or two good ratings or messages with non-unique identifiers. The final pair is not revealed to Bob.

At any later time, Alice may simultaneously publish one message and discard the other. It's important that the software handling this makes a strong effort to prevent saving a message after its pair has been published, as Alice needs this for plausible deniability: If Bob tries to find out who published a bad rating, he can ask people who have published ratings about him, but they can just point to any published good rating and claim that was their own. Bob could get around this by demanding they show him an unpublished bad rating (which would prove that if they published at all, it was a good rating); this is why Alice should not be able to save the unpublished member of a pair.

# ¿ Nov 9, 2008 23:20

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

ZorbaTHut posted:

First, while we have a working "rating" system, we don't have any kind of a "web of trust" system. It's pretty easily breakable by just generating a billion "this guy is awesome" messages - since there's no way to tell whether the person who wrote a message is a guy you trust or not, there isn't really a way to tell whether a message should be trusted or not.

Orthogonal problem. Trusting someone's ability to rank people accurately is completely different from trusting their in-game behaviour. Manage trust with a public-key-and-signed-affidavit system, like PGP.

You'd want to allow ratings to be either signed or unsigned, and have a (probably configurable) default weight for unsigned- or signed-by-unreachable- ratings.

If you want signatures and anonymous ratings, then you can have the software examine trust networks, identify medium-to-large-sized groups of people it is part of that have positive minimal intertrust, and negotiate to create a new pseudo-identity that everyone in the group holds the private key for, and everyone trusts with the same minimal intertrust they have with the rest of the group. Then anyone in that group can sign ratings with the pseudo-identity's key instead of their own, and plausibly claim someone else in the group published that rating, but the trust web still finds the signer and assigns it an appropriate trust weight (no worse than the path to the least-trusted person in the group).

You can probably score pseudo-identities based on the minimal intertrust they represent multiplied by the number of users known to hold the key; that gives you a function that approaches some "useful anonymity" metric which the software can use to decide what identities to use when signing rankings. There's an externality where you want to make sure that the group includes other people likely to issue rankings for the rankee; you probably need to defer to the user somehow for that.

ZorbaTHut posted:

Second, it relies on the ratee using the software also, which I can't guarantee. I'd like this to work on people who aren't using the software - obviously they won't be able to give out ratings, but they should be ratable, otherwise the entire thing kind of collapses.

You might be able to get away with just the pseudo-identity solution I posted above, and having ratings signed by the ranker (or ranker's pseudo-identity) rather than by the rankee. This opens up to allowing ranking-spam against a person, however.

A better solution is to allow rankings to be optionally signed by the rankee using the old protocol, in addition to optionally signed by the ranker (or a pseudo-identity). If the rankee is a user of the software (that is, if they have a published public key), then vastly reduce the weight (possibly to zero? you need some protection against people who publish a key then never agree to ranking exchanges, though. Better might be to make reputation from [-1, 1] but unsigned ranks can only shift it in the range [-0.5, 0.5] or so) on rankings not signed by them. So, you can rank people who don't use the software, but if they want protection against ranking-spam, they have incentive to use the software and publish a key. That not only lets them rank other people and view their own rank, it also protects them from spam and makes other users more confident that their ranking is genuine.

There are still a few issues. A person can create a pseudo-identity with a group of other people, then use that identity to sign positive rankings for himself. You probably want to forbid "self-signatures" of this form, so just enforce that pseudo-identities can't sign rankings on their members. That's a really hard problem, because it assumes that the machines of everyone who has a key for a given pseudo-identity are secure (otherwise someone could hack in to one, steal a key, and use that pseudo-identity to sign rankings on themselves). This is a very hard problem, and you need to get into serious revocation systems for trust webs and a complicated nested-identity publishing scheme. And there's pretty much nothing stopping someone from generating positive rankings for themself that are unsigned by a ranker or signed by a ranker that's not part of the trust web; all you can do is depend on the trust web to weight those poorly and limit their impact.

Edit: Oh yeah, there's a flaw in the protocol I had above for paired-rank-exchange. Alice sends Bob two down-ranks, Bob signs, sends them back, then demands a disclosure and protocol restart (to check if Alice is cheating), Alice simply disconnects and later publishes both down-ranks. Bob lacks an effective revocation system, and if we gave him one he could use it against published down-ranks and artifically boost his reputation. You have to depend on trusting the software here, or move to a doubly-blinded protocol. A simple augmentation may be that Bob uses a separate, unpublished key to sign all the responses that he intends to immediately demand disclosure on, so Alice can't usefully publish them; this is probably the best way to solve the problem, but it does add some overhead in terms of additional keys. Note that Bob has to sign them somehow, otherwise he has no real evidence that Alice isn't sending two down-ranks, then when asked to disclose, responding with a down-rank and an up-rank.

ShoulderDaemon fucked around with this message at 00:50 on Nov 10, 2008

# ¿ Nov 10, 2008 00:38

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

oldkike posted:

What kind of encryption do you use where Adecrypt(Bsign(X)) == Bsign(Adecrypt(X)) ?

There's a few methods, but the simplest is RSA and blinding multiplication.

Basically, Bob has an RSA key Bpri, Bpub, and n. Alice picks a random integer in [1, n] called Amul. Alice wants to get the message txt signed.

Alice computes blind = txt * Amul^Bpub mod n
Bob computes sblind = blind^Bpri mod n
Alice computes stxt = sblind/Amul mod n
With a little number theory, you can show stxt = txt^Bpri mod n, which is the RSA signing function.

And, uh, don't implement this from what I've said, because I'm kind of tired right now and probably made a typo. But it's called Chaum blind signatures, and you should be able to find a better-written description and proof with some google work.

# ¿ Nov 10, 2008 03:48

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Rocko Bonaparte posted:

This is a question about using curl, but I thought it might be answered here since I think anybody here who has done some automation has probably done this before. Suppose I want to access IBM's news on Google Finance. Your browser can go there at:

http://finance.google.com/finance?morenews=10&rating=1&q=NYSE:IBM

Now I want to retrieve that from the command line. Generally when I see '&' I assume it's time for curl.

I am trying:

curl -d "morenews=10" -d "rating=1" -d "q=NYSE:IBM" http://finance.google.com/finance > test.html

test.html will end up being the main google finance page. No good. What am I missing?

curl 'http://finance.google.com/finance?morenews=10&rating=1&q=NYSE:IBM'

It's a GET request, not a POST, so you just request the URL with no particular cleverness.

Edit: Just to be clear, this is a property of HTTP, not of curl; wget or indeed any web client behaves the same way. The only time you need to use curl's -d stuff is when the page requires POST data (and, consequently, could not be made into a [url][/url] link).

ShoulderDaemon fucked around with this message at 06:17 on Dec 8, 2008

# ¿ Dec 8, 2008 06:14

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Rocko Bonaparte posted:

I was trying wget on the full URL and was getting a 404. Is there something to it or should that have just worked?

If you ran wget http://finance.google.com/finance?morenews=10&rating=1&q=NYSE:IBM without the quotes around the URL, it'll parse as wget http://finance.google.com/finance?morenews=10 & rating=1 & q=NYSE:IBM, which runs wget http://finance.google.com/finance?morenews=10 in the background, resulting in a 404, sets the environment variable rating to 1, and sets the environment variable q to NYSE:IBM.

Edit: This is sort of a pet peeve of me, I have no idea why the GET syntax settled on using ampersand to separate query components, even though many shells have used that as a reserved character for ages. What makes it worse is that recently a new separator was proposed (which, of course, web browsers can't safely use at this point because the server code may be too old to understand it) and that wound up as semicolon, possibly the only character reserved by more shells than ampersand.

ShoulderDaemon fucked around with this message at 08:17 on Dec 8, 2008

# ¿ Dec 8, 2008 08:11

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

jeremiah johnson posted:

I would like to make a program that could solve cryptograms what would be a good language to use?

I've seen a few different things labelled as "cryptograms", so an example might help here. But most simple cryptographic puzzles rely heaving on text manipulation rather than bit manipulation, so Perl is probably as good a choice as anything.

# ¿ Dec 19, 2008 02:33

Adbot: ADBOT LOVES YOU

# ¿ Apr 29, 2024 05:26

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

EternalMoogle posted:

So, I see things like the visualizers in audio software (iTunes, WinAmp, etc), games like Audiosurf, and so on, and I'm wanting to learn more about how exactly those work. I'm sure there are websites with information on how to start playing with audio files, but it seems my google-fu is extremely weak on this subject, because I don't even know what to begin looking for. Can anyone point me toward some good starting resources?

I'm an undergrad CS major, so I'm kinda-sorta-experienced in the programming world. Just not with audio stuff.

You'll probably want to start by googling for some terms like "spectrum analyzer" and "fourier transform", or take a class on signal processing.

# ¿ Jan 1, 2009 22:23

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Ask General Programming Questions Not Worth Their Own Thread

«‹›6 »

Alan Greenspan posted:

more falafel please posted:

code:

code:

Incoherence posted:

Incoherence posted:

Scaevolus posted:

Incoherence posted:

code:

Scaevolus posted:

code:

nbv4 posted:

Bonus posted:

code:

code:

Jam2 posted:

Jam2 posted:

clockwork automaton posted:

Orlen posted:

Clock Explosion posted:

JoeNotCharles posted:

code:

JoeNotCharles posted:

code:

JoeNotCharles posted:

code:

code:

covener posted:

code:

6174 posted:

schnarf posted:

Orlen posted:

slovach posted:

Ugg boots posted:

code:

ZorbaTHut posted:

Sexxxy Sophitia posted:

code:

Mr. Jive posted:

Nahrix posted:

ZorbaTHut posted:

ZorbaTHut posted:

ZorbaTHut posted:

ZorbaTHut posted:

ZorbaTHut posted:

oldkike posted:

Rocko Bonaparte posted:

Rocko Bonaparte posted:

jeremiah johnson posted:

EternalMoogle posted: