text:
## Class MultiCurrencyAmount

• All Implemented Interfaces:
FxConvertible<CurrencyAmount>, Serializable, org.joda.beans.Bean, org.joda.beans.ImmutableBean

public final class MultiCurrencyAmount
extends Object
implements FxConvertible<CurrencyAmount>, org.joda.beans.ImmutableBean, Serializable
A map of currency amounts keyed by currency.

This is a container holding multiple CurrencyAmount instances. The amounts do not necessarily have the same worth or value in each currency.

This class is immutable and thread-safe.

Serialized Form
• ### Nested Class Summary

Nested Classes
Modifier and Type Class Description
static class  MultiCurrencyAmount.Meta
The meta-bean for MultiCurrencyAmount.
• ### Method Summary

All Methods
Modifier and Type Method Description
boolean contains(Currency currency)
Checks if this multi-amount contains an amount for the specified currency.
CurrencyAmount convertedTo(Currency resultCurrency, FxRateProvider rateProvider)
Converts this amount to an equivalent amount the specified currency.
static MultiCurrencyAmount empty()
Obtains an empty MultiCurrencyAmount.
boolean equals(Object obj)
CurrencyAmount getAmount(Currency currency)
Gets the CurrencyAmount for the specified currency, throwing an exception if not found.
CurrencyAmount getAmountOrZero(Currency currency)
Gets the CurrencyAmount for the specified currency, returning zero if not found.
ImmutableSortedSet<CurrencyAmount> getAmounts()
Gets the set of currency amounts.
ImmutableSet<Currency> getCurrencies()
Gets the set of stored currencies.
int hashCode()
MultiCurrencyAmount mapAmounts(DoubleUnaryOperator mapper)
Applies an operation to the amounts.
MultiCurrencyAmount mapCurrencyAmounts(UnaryOperator<CurrencyAmount> operator)
Applies an operation to the currency amounts.
static MultiCurrencyAmount.Meta meta()
The meta-bean for MultiCurrencyAmount.
MultiCurrencyAmount.Meta metaBean()
MultiCurrencyAmount minus(CurrencyAmount amountToSubtract)
Returns a copy of this MultiCurrencyAmount with the specified amount subtracted.
MultiCurrencyAmount minus(Currency currency, double amountToAdd)
Returns a copy of this MultiCurrencyAmount with the specified amount subtracted.
MultiCurrencyAmount minus(MultiCurrencyAmount amountToSubtract)
Returns a copy of this MultiCurrencyAmount with the specified amount subtracted.
MultiCurrencyAmount multipliedBy(double factor)
Returns a copy of this MultiCurrencyAmount with all the amounts multiplied by the factor.
MultiCurrencyAmount negated()
Returns a copy of this CurrencyAmount with the amount negated.
static MultiCurrencyAmount of(CurrencyAmount... amounts)
Obtains an instance from an array of CurrencyAmount objects.
static MultiCurrencyAmount of(Currency currency, double amount)
Obtains an instance from a currency and amount.
static MultiCurrencyAmount of(Iterable<CurrencyAmount> amounts)
Obtains an instance from a list of CurrencyAmount objects.
static MultiCurrencyAmount of(Map<Currency,Double> map)
Obtains an instance from a map of currency to amount.
MultiCurrencyAmount plus(CurrencyAmount amountToAdd)
Returns a copy of this MultiCurrencyAmount with the specified amount added.
MultiCurrencyAmount plus(Currency currency, double amountToAdd)
Returns a copy of this MultiCurrencyAmount with the specified amount added.
MultiCurrencyAmount plus(MultiCurrencyAmount amountToAdd)
Returns a copy of this MultiCurrencyAmount with the specified amount added.
int size()
Gets the number of stored amounts.
Stream<CurrencyAmount> stream()
Returns a stream over the currency amounts.
ImmutableSortedMap<Currency,Double> toMap()
Converts this MultiCurrencyAmount to a map keyed by currency.
static Collector<CurrencyAmount,?,MultiCurrencyAmount> toMultiCurrencyAmount()
Returns a collector that can be used to create a multi-currency amount from a stream of amounts.
String toString()
Gets the amount as a string.
static MultiCurrencyAmount total(Iterable<CurrencyAmount> amounts)
Obtains an instance from the total of a list of CurrencyAmount objects.
• ### Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait
• ### Methods inherited from interface org.joda.beans.Bean

property, propertyNames
• ### Method Detail

• #### empty

public static MultiCurrencyAmount empty()
Obtains an empty MultiCurrencyAmount.
Returns:
the empty instance
• #### of

public static MultiCurrencyAmount of(Currency currency,
double amount)
Obtains an instance from a currency and amount.
Parameters:
currency - the currency
amount - the amount
Returns:
the amount
• #### of

public static MultiCurrencyAmount of(CurrencyAmount... amounts)
Obtains an instance from an array of CurrencyAmount objects.

It is an error for the input to contain the same currency twice.

Parameters:
amounts - the amounts
Returns:
the amount
• #### of

public static MultiCurrencyAmount of(Iterable<CurrencyAmount> amounts)
Obtains an instance from a list of CurrencyAmount objects.

It is an error for the input to contain the same currency twice.

Parameters:
amounts - the amounts
Returns:
the amount
• #### of

public static MultiCurrencyAmount of(Map<Currency,Double> map)
Obtains an instance from a map of currency to amount.
Parameters:
map - the map of currency to amount
Returns:
the amount
• #### total

public static MultiCurrencyAmount total(Iterable<CurrencyAmount> amounts)
Obtains an instance from the total of a list of CurrencyAmount objects.

If the input contains the same currency more than once, the amounts are added together. For example, an input of (EUR 100, EUR 200, CAD 100) would result in (EUR 300, CAD 100).

Parameters:
amounts - the amounts
Returns:
the amount
• #### toMultiCurrencyAmount

public static Collector<CurrencyAmount,?,MultiCurrencyAmount> toMultiCurrencyAmount()
Returns a collector that can be used to create a multi-currency amount from a stream of amounts.

If the input contains the same currency more than once, the amounts are added together. For example, an input of (EUR 100, EUR 200, CAD 100) would result in (EUR 300, CAD 100).

Returns:
the collector
• #### getCurrencies

public ImmutableSet<Currency> getCurrencies()
Gets the set of stored currencies.
Returns:
the set of currencies in this amount
• #### size

public int size()
Gets the number of stored amounts.
Returns:
the number of amounts
• #### contains

public boolean contains(Currency currency)
Checks if this multi-amount contains an amount for the specified currency.
Parameters:
currency - the currency to find
Returns:
true if this amount contains a value for the currency
• #### getAmount

public CurrencyAmount getAmount(Currency currency)
Gets the CurrencyAmount for the specified currency, throwing an exception if not found.
Parameters:
currency - the currency to find an amount for
Returns:
the amount
Throws:
IllegalArgumentException - if the currency is not found
• #### getAmountOrZero

public CurrencyAmount getAmountOrZero(Currency currency)
Gets the CurrencyAmount for the specified currency, returning zero if not found.
Parameters:
currency - the currency to find an amount for
Returns:
the amount
• #### plus

public MultiCurrencyAmount plus(Currency currency,
double amountToAdd)
Returns a copy of this MultiCurrencyAmount with the specified amount added.

This adds the specified amount to this monetary amount, returning a new object. If the currency is already present, the amount is added to the existing amount. If the currency is not yet present, the currency-amount is added to the map. The addition uses standard double arithmetic.

This instance is immutable and unaffected by this method.

Parameters:
currency - the currency to add to
amountToAdd - the amount to add
Returns:
an amount based on this with the specified amount added
• #### plus

public MultiCurrencyAmount plus(CurrencyAmount amountToAdd)
Returns a copy of this MultiCurrencyAmount with the specified amount added.

This adds the specified amount to this monetary amount, returning a new object. If the currency is already present, the amount is added to the existing amount. If the currency is not yet present, the currency-amount is added to the map. The addition uses standard double arithmetic.

This instance is immutable and unaffected by this method.

Parameters:
amountToAdd - the amount to add
Returns:
an amount based on this with the specified amount added
• #### plus

public MultiCurrencyAmount plus(MultiCurrencyAmount amountToAdd)
Returns a copy of this MultiCurrencyAmount with the specified amount added.

This adds the specified amount to this monetary amount, returning a new object. If the currency is already present, the amount is added to the existing amount. If the currency is not yet present, the currency-amount is added to the map. The addition uses standard double arithmetic.

This instance is immutable and unaffected by this method.

Parameters:
amountToAdd - the amount to add
Returns:
an amount based on this with the specified amount added
• #### minus

public MultiCurrencyAmount minus(Currency currency,
double amountToAdd)
Returns a copy of this MultiCurrencyAmount with the specified amount subtracted.

This subtracts the specified amount from this monetary amount, returning a new object. If the currency is already present, the amount is subtracted from the existing amount. If the currency is not yet present, the negated amount is included. The subtraction uses standard double arithmetic.

This instance is immutable and unaffected by this method.

Parameters:
currency - the currency to subtract from
amountToAdd - the amount to subtract
Returns:
an amount based on this with the specified amount subtracted
• #### minus

public MultiCurrencyAmount minus(CurrencyAmount amountToSubtract)
Returns a copy of this MultiCurrencyAmount with the specified amount subtracted.

This subtracts the specified amount from this monetary amount, returning a new object. If the currency is already present, the amount is subtracted from the existing amount. If the currency is not yet present, the negated amount is included. The subtraction uses standard double arithmetic.

This instance is immutable and unaffected by this method.

Parameters:
amountToSubtract - the amount to subtract
Returns:
an amount based on this with the specified amount subtracted
• #### minus

public MultiCurrencyAmount minus(MultiCurrencyAmount amountToSubtract)
Returns a copy of this MultiCurrencyAmount with the specified amount subtracted.

This subtracts the specified amount from this monetary amount, returning a new object. If the currency is already present, the amount is subtracted from the existing amount. If the currency is not yet present, the negated amount is included. The subtraction uses standard double arithmetic.

This instance is immutable and unaffected by this method.

Parameters:
amountToSubtract - the amount to subtract
Returns:
an amount based on this with the specified amount subtracted
• #### multipliedBy

public MultiCurrencyAmount multipliedBy(double factor)
Returns a copy of this MultiCurrencyAmount with all the amounts multiplied by the factor.

This instance is immutable and unaffected by this method.

Parameters:
factor - the multiplicative factor
Returns:
an amount based on this with all the amounts multiplied by the factor
• #### negated

public MultiCurrencyAmount negated()
Returns a copy of this CurrencyAmount with the amount negated.

This takes this amount and negates it. If any amount is 0.0 or -0.0 the negated amount is 0.0.

This instance is immutable and unaffected by this method.

Returns:
an amount based on this with the amount negated
• #### stream

public Stream<CurrencyAmount> stream()
Returns a stream over the currency amounts.

Returns:
a stream over the individual amounts
• #### mapAmounts

public MultiCurrencyAmount mapAmounts(DoubleUnaryOperator mapper)
Applies an operation to the amounts.

This is generally used to apply a mathematical operation to the amounts. For example, the operator could multiply the amounts by a constant, or take the inverse.

   multiplied = base.mapAmount(value -> value * 3);

Parameters:
mapper - the operator to be applied to the amounts
Returns:
a copy of this amount with the mapping applied to the original amounts
• #### mapCurrencyAmounts

public MultiCurrencyAmount mapCurrencyAmounts(UnaryOperator<CurrencyAmount> operator)
Applies an operation to the currency amounts.

The operator is called once for each currency in this amount. The operator may return an amount with a different currency. The result will be the total of the altered amounts.

Parameters:
operator - the operator to be applied to the amounts
Returns:
a copy of this amount with the mapping applied to the original amounts
• #### convertedTo

public CurrencyAmount convertedTo(Currency resultCurrency,
FxRateProvider rateProvider)
Converts this amount to an equivalent amount the specified currency.

The result will be expressed in terms of the given currency. If conversion is needed, the provider will be used to supply the FX rate.

Specified by:
convertedTo in interface FxConvertible<CurrencyAmount>
Parameters:
resultCurrency - the currency of the result
rateProvider - the provider of FX rates
Returns:
the converted instance, which should be expressed in the specified currency
Throws:
RuntimeException - if no FX rate could be found
• #### toMap

public ImmutableSortedMap<Currency,Double> toMap()
Converts this MultiCurrencyAmount to a map keyed by currency.
Returns:
the amounts in a map keyed by currency
• #### toString

public String toString()
Gets the amount as a string.

The format includes each currency-amount.

Overrides:
toString in class Object
Returns:
the currency amount
• #### meta

public static MultiCurrencyAmount.Meta meta()
The meta-bean for MultiCurrencyAmount.
Returns:
the meta-bean, not null
• #### metaBean

public MultiCurrencyAmount.Meta metaBean()
Specified by:
metaBean in interface org.joda.beans.Bean
• #### getAmounts

public ImmutableSortedSet<CurrencyAmount> getAmounts()
Gets the set of currency amounts. Each currency will occur only once, as per a map keyed by currency.
Returns:
the value of the property, not null
• #### equals

public boolean equals(Object obj)
Overrides:
equals in class Object
• #### hashCode

public int hashCode()
Overrides:
hashCode in class Object


text:
POJ-1860 Currency Exchange 【spfa判负环】

Description

Several currency exchange points are working in our city. Let us suppose that each point specializes in two particular currencies and performs exchange operations only with these currencies. There can be several points specializing in the same pair of currencies. Each point has its own exchange rates, exchange rate of A to B is the quantity of B you get for 1A. Also each exchange point has some commission, the sum you have to pay for your exchange operation. Commission is always collected in source currency.
For example, if you want to exchange 100 US Dollars into Russian Rubles at the exchange point, where the exchange rate is 29.75, and the commission is 0.39 you will get (100 - 0.39) * 29.75 = 2963.3975RUR.
You surely know that there are N different currencies you can deal with in our city. Let us assign unique integer number from 1 to N to each currency. Then each exchange point can be described with 6 numbers: integer A and B - numbers of currencies it exchanges, and real RAB, CAB, RBA and CBA - exchange rates and commissions when exchanging A to B and B to A respectively.
Nick has some money in currency S and wonders if he can somehow, after some exchange operations, increase his capital. Of course, he wants to have his money in currency S in the end. Help him to answer this difficult question. Nick must always have non-negative sum of money while making his operations.

Input

The first line of the input contains four numbers: N - the number of currencies, M - the number of exchange points, S - the number of currency Nick has and V - the quantity of currency units he has. The following M lines contain 6 numbers each - the description of the corresponding exchange point - in specified above order. Numbers are separated by one or more spaces. 1<=S<=N<=100, 1<=M<=100, V is real number, 0<=V<=103.
For each point exchange rates and commissions are real, given with at most two digits after the decimal point, 10-2<=rate<=102, 0<=commission<=102.
Let us call some sequence of the exchange operations simple if no exchange point is used more than once in this sequence. You may assume that ratio of the numeric values of the sums at the end and at the beginning of any simple sequence of the exchange operations will be less than 104.

Output

If Nick can increase his wealth, output YES, in other case output NO to the output file.

Sample Input

3 2 1 20.0
1 2 1.00 1.00 1.00 1.00
2 3 1.10 1.00 1.10 1.00

Sample Output

YES

题解：spfa判负环，了解spfa的原理，判断是否存在在一个环中货币能升值。代码：
 1 #include<iostream>
2 #include<algorithm>
3 #include<cstdio>
4 #include<cstring>
5 #include<queue>
6 #include<vector>
7 #include<set>
8 using namespace std;
9 #define M(a, b) memset(a, b, sizeof(a))
10 #define INF 0x3f3f3f3f
11 const int N = 100 + 5;
12 double d[N], V;
13 int n, m, cnt[N], s;
14 bool inq[N];
15 struct Node {
16     int to;
17     double r, c;
18 };
19 vector<Node> G[N];
20
21 void AddEdge(int u, int v, double r, double c) {
22     G[u].push_back({v, r, c});
23 }
24
25 bool spfa(int s, double V) {
26     M(d, 0); M(cnt, 0); M(inq, 0);
27     queue<int> q; q.push(s);
28     inq[s] = 1; cnt[s] = 1; d[s] = V;
29     while (!q.empty()) {
30         int u = q.front(); q.pop(); inq[u] = 0;
31         for (int i = 0; i < G[u].size(); ++i) {
32             Node &e = G[u][i];
33             if (d[e.to] < (d[u]-e.c)*e.r) {
34                 d[e.to] = (d[u]-e.c)*e.r;
35                 if (!inq[e.to]) {
36                     inq[e.to] = 1;
37                     q.push(e.to);
38                     if (++cnt[e.to]>n) return true;
39                 }
40             }
41         }
42     }
43     return false;
44 }
45
46 int main() {
47     while (~scanf("%d%d", &n, &m)) {
48         for (int i = 0; i <= n; ++i) G[i].clear();
49         scanf("%d%lf", &s, &V);
50         int u, v;
51         double r1, c1, r2, c2;
52         for (int i = 0; i < m; ++i) {
53             scanf("%d%d%lf%lf%lf%lf", &u, &v, &r1, &c1, &r2, &c2);
61 }

format: plain


text:
### Abstracts of papers presented at the international atomic energy agency conference on the use of radioisotopes in the physical sciences and industry: Copenhagen, 6???17 September 1960

Title Abstracts of papers presented at the international atomic energy agency conference on the use of radioisotopes in the physical sciences and industry: Copenhagen, 6?��17 September 1960
Author:
The International Journal of Applied Radiation and Isotopes, 1960
1960
http://www.sciencedirect.com/science/article/pii/0020708X6090034X
More details:

### Program the Annual Meeting of the American Gastroenterological Association and Digestive Disease Week

Title Program the Annual Meeting of the American Gastroenterological Association and Digestive Disease Week
Author:
Gastroenterology, 1995
1995
http://www.sciencedirect.com/science/article/pii/0016508595226699
More details:
ISBN0016-5085
The American Gastroenterological Association and Digestive Disease Week

### Liquid column chromatography

Title Liquid column chromatography
Author:
Journal of Chromatography A, 1991
1991
http://www.sciencedirect.com/science/article/pii/002196739180040N
More details:

### Analytical biotechnology

Title Analytical biotechnology
Author:
Current Opinion in Biotechnology, 1996
1996
http://www.sciencedirect.com/science/article/pii/S0958166996801078
More details:

### Fundamentals of the Physics of Solids Volume II : Electronic Prperties

Title Fundamentals of the Physics of Solids Volume II : Electronic Prperties
Author:
, Springer 2009
2009
http://www.springer.com/978-3-540-85315-2
More details:
ISBN978-3-540-85315-2

### Radioactivity measurements principles and practice

Title Radioactivity measurements principles and practice
Author:
International Journal of Radiation Applications and Instrumentation. Part A. Applied Radiation and Isotopes, January 1988
1988
More details:

### Magnetic fluids bibliography

Title Magnetic fluids bibliography
Author:
Journal of Magnetism and Magnetic Materials, 1983
1983
http://www.sciencedirect.com/science/article/pii/0304885383904328
More details:

### Liquid column chromatography

Title Liquid column chromatography
Author:
Journal of Chromatography A, 1985
1985
http://www.sciencedirect.com/science/article/pii/S0021967300915310
More details:

### Section 1 - Directory of manufacturers, country by country

Title Section 1 - Directory of manufacturers, country by country
Author:
, Elsevier 1990
1990
http://www.sciencedirect.com/science/article/pii/B9780948577390500063
More details:
ISBN978-0-948577-39-0

### Section 2 - Directory of agents and representatives, country by country

Title Section 2 - Directory of agents and representatives, country by country
Author:
, Elsevier 1993
1993
http://www.sciencedirect.com/science/article/pii/B9781856171755500062
More details:
ISBN978-1-85617-175-5

### Chapter 7 Current phosphor device technology

Title Chapter 7 Current phosphor device technology
Author:
, Elsevier 2004
2004
http://www.sciencedirect.com/science/article/pii/S0169315804800100
More details: Publisher Summary This chapter discusses the latest devices and the phosphors currently employed in them. Many phosphors that have been developed for the particular display purposes are discussed. The chapter discusses how the light sources such as, incandescent and fluorescent lamps are going to become obsolete as the quality of light-emitting diodes (LEDs) improves. The phosphors will continue to be used to make light emitting \{LED\} light sources. The main advantage of the \{LED\} lamp is that, it uses milliwatts of power, compared to watts of power for the incandescent and fluorescent lamp. The chapter surveys the present-day devices utilizing phosphors emphasizing the recent improvements made in cathode-ray tubes (CRT) and fluorescent lamps. The devices that depend upon thin film deposition for the manufacture of the appliance are described. The devices that use phosphors responding to high energy photons like X-rays and gamma rays (high energy X-rays) are described. The chapter also describes scintillators that are the phosphors used to detect $\alpha$, $\beta$ and $\gamma$ rays from incident sources.

### \CHAPTER\ 6 - Classification of \EDTA\ Complexes

Title \CHAPTER\ 6 - Classification of \EDTA\ Complexes
Author:
, Pergamon 1982
1982
http://www.sciencedirect.com/science/article/pii/B9780080262772500121
More details:
ISBN978-0-08-026277-2

### Chapter 13 Two-Dimensional Crystallization Of Particulates And Proteins

Title Chapter 13 Two-Dimensional Crystallization Of Particulates And Proteins
Author:
, Elsevier 2001
2001
http://www.sciencedirect.com/science/article/pii/S1383730301800545
More details: Publisher Summary The chapter overviews the methods for producing ordered two-dimensional arrays from colloid particles and proteins in relation to their physical mechanisms and driving forces. The chapter focuses on the method for obtaining particle and protein two- dimensional arrays in evaporating liquid suspension films. The respective mechanism of two-dimensional crystallization is based on the fact that the decrease of the film thickness (because of evaporation) forces the particles to enter and/or deform the liquid interface that automatically ?ǣswitches on?�? the strong attraction because of the capillary immersion force. The chapter describes the the occurrence and advantages of two-dimensional array formation over a liquid substrate: fluorinated oil and mercury. The particle size separation during two-dimensional crystallization and the methods for obtaining large two-dimensional crystalline coatings on solid substrates are described in the chapter. This chapter considers only the formation of two-dimensional arrays in free foam films and their observation by electron cryomicroscopy, which ensures an excellent structure preservation of delicate vesicles or molecular complexes. The chapter reviews the various applications of particulate two-dimensional arrays in optics, optoelectronics, nano-lithography, microcontact printing, in fabrication of nanostructured surfaces for catalytic films and solar cells, as well as the usage of protein two-dimensional crystals for immunosensors and extremely isoporous ultrafiltration membranes?��for creation of bioelectronic and biophotonic devices.

### Numerical simulations of vortex-induced vibration on flexible cylinders

Title Numerical simulations of vortex-induced vibration on flexible cylinders
Author: Yamamoto, C.T.; Meneghini, J.R.; Saltara, F.; Fregonesi, R.a. & Ferrari, J.a.
Journal of Fluids and Structures, May 2004
2004


text:
# . Maximizing Profit A community bird-watching societymakes and sells simple bird feeders to raise money for itsconservation activities. The materials for each feeder cost $6,and the society sells an average of 20 per week at a price of$10 each. The society has been considering raising the price,so it conducts a survey and finds that for every dollarincrease, it will lose 2 sales per week.(a) Find a function that models weekly profit in terms ofprice per feeder.(b) What price should the society charge for each feederto maximize profits? What is the maximum weeklyprofit?

Question

. Maximizing Profit A community bird-watching society
makes and sells simple bird feeders to raise money for its
conservation activities. The materials for each feeder cost $6, and the society sells an average of 20 per week at a price of$10 each. The society has been considering raising the price,
so it conducts a survey and finds that for every dollar
increase, it will lose 2 sales per week.
(a) Find a function that models weekly profit in terms of
price per feeder.
(b) What price should the society charge for each feeder
to maximize profits? What is the maximum weekly
profit?


text:
Random Access Of Lines In A Compressed File Having A Custom Tabulated Format?
3
3
Entering edit mode
10.1 years ago
tflutre ▴ 540

Hello, I am working with large files (eg. 10^7 lines) having a custom tabulated format (eg. geneid TAB SNPid TAB SNPcoord TAB measurex TAB measure_y TAB ...). And I have two wishes / requirements:

• compress the files to save disk space;
• quickly access some lines that are not in the order in which they appear in the file.

I am coding in C++. Up to now, I was using Gzstream to easily read gzipped files (I am too much of a beginner to try to use Zlib directly). But it doesn't allow random access. Thus, I am still using uncompressed files. Typically, I first go through the whole file and record the stream position of the lines I am interested in (using tellg). And then, I access these lines using the stream positions previously recorded (using getline). However, I would like to be able to do the same on compressed files.

From what I read (eg. mentioned here), BGZF allows to do exactly that. I could thus theoretically use this in my code. Has anyone tried to do it? As I am more a geneticist than a programmer, is there any code snippet somewhere I could try to reuse?

Otherwise, I can also design my own minimal binary format. Although it would be quick to implement, it is ad-hoc... Should I rather look into the HDF5 format (eg. here)? Using h5dump, it seems possible to access only to a subset of the data. But has anyone tried to use the functions directly from his C/C++ code?

tabix c • 3.5k views
1
Entering edit mode

When accessing the file, if you can order your seeks so that they are sequential by file order they will be much faster. If that's not possible, putting the data on an SSD which is very quick for seeks can speed things up.

6
Entering edit mode
10.1 years ago

The code for samtools contains a very simple API (open, seek, close...) for bgzf: http://samtools.svn.sourceforge.net/viewvc/samtools/trunk/samtools/ (see bgzf.h and bgzf.c)

In C++, you can also simply wrap this code in a class to make it more OO oriented. For example (not tested)

compile:

 g++ -c xbgzf.cpp -I /path/to/samtools-0.1.18

#ifndef XBGZF_H_
#define XBGZF_H_

#include <stdint.h>
class BgzFile
{
private:
void* _ptr;
public:
BgzFile(int fd,const char* m);
BgzFile(const char* filename,const char* m);
virtual ~BgzFile();
virtual void close();
virtual int write(void* data,int length);
virtual int64_t tell();
virtual int64_t seek(int64_t pos, int where);
virtual void set_cache_size(int cache_size);
virtual int getc();
};

source:

/*
* xbgzf.cpp
*
*  Created on: Oct 28, 2011
*      Author: lindenb
*/
#include <sstream>
#include <cstring>
#include <cerrno>
#include <stdexcept>
#include <bgzf.h>
#include "xbgzf.h"
using namespace std;

#define CASTPTR ((BGZF *)(this->_ptr))

BgzFile::BgzFile(const char* filename,const char* mode):_ptr(NULL)
{
_ptr=::bgzf_open(filename,mode);
if(_ptr==NULL)
{
ostringstream os;
os << "Cannot open "<< filename << " " << strerror(errno);
throw runtime_error(os.str());
}
}
BgzFile::BgzFile(int fd,const char* mode):_ptr(NULL)
{
_ptr=::bgzf_fdopen(fd,mode);
if(_ptr==NULL)
{
ostringstream os;
os << "Cannot open fd " << strerror(errno);
throw runtime_error(os.str());
}
}
BgzFile::~BgzFile()
{
close();
}
void BgzFile::close()
{
if(_ptr!=NULL) ::bgzf_close(CASTPTR);
_ptr=NULL;
}
{
}

int BgzFile::write(void* data,int length)
{
return _ptr==NULL? -1:bgzf_write(CASTPTR,data,length);
}
int64_t BgzFile::tell()
{
return _ptr==NULL? -1:bgzf_tell(CASTPTR);
}
int64_t BgzFile::seek(int64_t pos, int where)
{
return _ptr==NULL? -1:bgzf_seek(CASTPTR,pos,where);
}
void BgzFile::set_cache_size(int cache_size)
{
if( _ptr!=NULL) ::bgzf_set_cache_size(CASTPTR,cache_size);
}
int BgzFile::getc()
{
return _ptr==NULL? -1:bgzf_getc(CASTPTR);
}

About HDF : as far as I've understand HDF, it is a standard way to store some binary data into a structured file. But it has no capabilities to search for a given value. You'll have to implement the logic for searching by yourself. One more word: HDF is a headache for programming (many resources have to be copied/released/etc...) even for doing simple things.

0
Entering edit mode

@Pierre Lindenbaum Thanks a lot! So first I need to go through the whole file using read, and recording the beginning of lines I'm interested in using tell. And then, in a later stage, I directly access those lines using seek, right? (Knowing that I need to use length properly to be sure I read the entire line, of course.)

0
Entering edit mode

yes, and you can also stores the indexes of the lines in a second binary file where all the records(=offsets in the 1st file) have the same length(sizeof(int64_t) ) (so you just have to seek(index*sizeof(int64_t)); )

2
Entering edit mode
10.0 years ago
tflutre ▴ 540

Thanks to everyone that proposed a solution! Finally, I decided to use the bgzip utility to compress my large input files, and then I implemented a bgzf_getline function that uses bgzf_getc().

1) to obtain and compile bgzip:

# download the source code from SAMTOOLS
wget -O bgzip.c http://samtools.svn.sourceforge.net/viewvc/samtools/trunk/samtools/bgzip.c?revision=998
wget -O bgzf.h http://samtools.svn.sourceforge.net/viewvc/samtools/trunk/samtools/bgzf.h?revision=998
wget -O bgzf.c http://samtools.svn.sourceforge.net/viewvc/samtools/trunk/samtools/bgzf.c?revision=998
wget -O khash.h http://samtools.svn.sourceforge.net/viewvc/samtools/trunk/samtools/khash.h?revision=998

# compile bgzip (require ZLIB)
gcc -Wall bgzf.c bgzip.c -o bgzip -lz
./bgzip

2) to test it:

# test it: zcat/gunzip can decompress a file compressed with bgzip (converse is wrong)
ls ~ > test.txt
./bgzip test.txt
zcat test.txt.gz
gunzip test.txt.gz
./bgzip test.txt
./bgzip -d test.txt.gz

3) here is my bgzf_getline function (I'm sure it's not the best way to code it, notably because it mixes C and C++ functions code, but it works):

void bgzf_getline (BGZF * stream, string & line)
{
line.erase();
int c = -1, i = 0;
char * p = (char *) malloc (1);
if (p == NULL)
{
fprintf (stderr, "ERROR: can't allocate memory\n");
exit (1);
}
while (true)
{
++i;
c = bgzf_getc (stream);
if (c == -2)
{
fprintf (stderr, "ERROR: can't read %i-th character\n", i);
exit (1);
}
if (c == -1)  // reach end of file
break;
if (c == 10)  // reach end of line
break;
//    printf ("byte #%i: %i %c\n", i, c, c);
sprintf (p, "%c", c);
line.append(p);
}
free (p);
}

4) finally, here is a gist of a dummy program showing how to use all this in practice:

https://gist.github.com/1434187

0
Entering edit mode

A more efficient implementation of a getline() is here: https://github.com/attractivechaos/klib/blob/master/bgzf.c at the end of the file. But I guess most would not care about this difference. This version of bgzf.c also kills the dependency to khash.h.

0
Entering edit mode

Thanks, I had a look at your bgzf_getline(), but what does the argument delim correspond to? And why the third argument is of type kstring_t and not char *? By any chance, would you have an example of using this function somewhere?

1
Entering edit mode
10.1 years ago
brentp 23k

You might use tabix directly (which uses bgzf), and save yourself some programming. You can index your file and then do queries on it quite easily from the command-line.

If you do use bgzf.h, I think you'll see it's quite simple, if you can open a file in C, you can use bgzf:

int bgzf_read(BGZF* fp, void* data, int length);
int bgzf_write(BGZF* fp, const void* data, int length);
#define bgzf_tell(fp) ((fp->block_address << 16) | (fp->block_offset & 0xFFFF))
int64_t bgzf_seek(BGZF* fp, int64_t pos, int where);

etc.

0
Entering edit mode

right, but note that tabix will only work if you have the columns chrom/start/end

0
Entering edit mode

It supports VCF, where supposedly, it just uses start == end. And either the data has a chromosome, or one could be faked. But, I'm lazy like that.

0
Entering edit mode

@brentp Thanks! Ok, indeed using the C code directly may be enough. I will start a small example to test it then. The only issue with read is that I need to specify length and it can be shorter or longer than an actual uncompressed line, right? So I could also use bgzf_getc and stop when I encounter 'n', no?

0
Entering edit mode

You can use bgzf_getc(). A little faster way is to use ti_readline() in index.c. But the latter is also a little more complicated.


text: dc.contributor.author Karasu Uysal, Ayben dc.contributor.author ALICE, Collaboration dc.date.accessioned 2019-07-05T11:05:47Z dc.date.available 2019-07-05T11:05:47Z dc.date.issued 2014 dc.identifier.uri https://hdl.handle.net/20.500.12498/483 dc.description.abstract Inclusive J/ψ production has been studied with the ALICE detector in p-Pb collisions at the nucleon–nucleon center of mass energy √sNN = 5.02TeV at the CERN LHC. The measurement is performed in the center of mass rapidity domains 2.03 < ycms < 3.53 and −4.46 < ycms < −2.96, down to zero transverse momentum, studying the μ+μ− decay mode. In this paper, the J/ψ production cross section and the nuclear modification factor RpPb for the rapidities under study are presented. While at forward rapidity, corresponding to the proton direction, a suppression of the J/ψ yield with respect to binary-scaled pp collisions is observed, in the backward region no suppression is present. The ratio of the forward and backward yields is also measured differentially in rapidity and transverse momentum. Theoretical predictions based on nuclear shadowing, as well as on models including, in addition, a contribution from partonic energy loss, are in fair agreement with the experimental results. en_US dc.relation 10.1007/JHEP02(2014)073 en_US dc.subject Relativistic heavy ion physics, Heavy Ions, Charm physics en_US dc.title J/ψ production and nuclear effects in p-Pb collisions at √sNN=5.02 TeV en_US dc.type Article en_US eperson.orcidid 0000-0001-6297-2532 en_US


text:
Phonics: Consonants b/k/s/r/f/l

In this consonants learning exercise, students pick one of the letters from the box to finish the words. Students pick from the letters b, k, s, r, f, and l. Students then draw a picture for the last 2 words.

Concepts

Resource Details


text:
0%

## 总结

• 新的detection方法的特点
• 利用了高拟合能力的卷积神经网络
• 缓解了训练detection任务数据量少的问题

### 物体定位问题

• 当成回归问题做——效果不好
• 用滑动窗口做——新的数据集图片比较大，不适合

• (用selective search)生成proposals
• 通过CNN对每个proposals生成固定长度的特征向量
• 用多个SVM判定向量是否属于特定类别
• 非极大值抑制筛选最终结果

### 数据量少的问题

• 先使用无监督训练，然后有监督fine-tuning

• 先用大量的无关classification数据训练网络初始参数
• 然后用特定类别有监督fine-tuning
• 迁移学习思想

### 可拓展性

• 生成proposal的时候是类别无关的
• CNN抽取特征的时候是类别无关的
• 最后的SVM判别是和类别数量相关，但只是线性相关
• 非极大值抑制过程也是线性相关
• 所以在目标类别很多的时候依旧能保证高效率，而不用去做近似计算

### 训练细节

#### CNN fine-tuning

• 把预训练的最后一层替换为目标类别数+1（背景算作一个类别）的分类层
• 所有和标记框IoU >= 0.5的proposal当做标记框所在类别的正样本否则当做负样本
• 学习率是预训练阶段的十分之一（0.001）
• 用32个正样本和96个负样本组成一个128的batch（这个比例主要是因为正样本少）

#### 特征分类

• 比fine-tuning的样本筛选更加严格
• 只有标记框抽取出来的特征当做正样本
• 与标记框IoU低于0.3(grid search出来的)的当做负样本
• IoU大于0.3但是小于1的扔掉

fine-tuning的样本选取方式不适合用于精确定位位置，所以单独训练模型去干这个事

### 特征可视化

• 选定一个特征（本文选取的是$pool_5$里的特征）
• 用大量的proposal过神经网络，得到这个特征的值
• 按特征值从大到小排列
• 非极大值抑制筛选proposal
• 把较大的proposal输出即为此特征的抽取信息的直观表现

### 分类特征值选择

• CNN最后的抽象特征有多层，本文对用不同的特征作为分类特征做了实验
• 如果没有经过fine-tuning那么用靠前网络层的更好($fc_6 > fc_7$)
• 经过fine-tuning的就用后面层作为分类特征值

### 网络结构选择

CNN作为特征抽取器，其结构对于最后的效果有非常大的影响

### bounding-box回归

• 用中心点x, y坐标，方框长和宽四维数据去定义边框
• 训练四个映射，把四维数据映射为真实值
• 用CNN $pool_5$的值代表proposal信息
• 采用LR模型
• 只把proposal和真实边框IoU大于等于0.6的当做训练数据
• 正则化参数很重要

### 与OverFeat对比

• OverFeat用的是multi-scale pyramid而不是selective search
• OverFeat是为每个类别分别训练一个bounding-box regression模型

### VOC测试结果

• time: 13000ms
• VOC 2010: 53.7%
• VOC 2011&2012: 53.3%
• VOC 2013: 31.4%

## Abstract

propose a detection algorithm:

• one can apply high-capacity convolutional neural networks (CNNs) to bottom-up region proposals in order to localize and segment objects
• when labeled training data is scarce, supervised pre-training for an auxiliary task, followed by domain-specific fine-tuning, yields a significant performance boost

RCNN: Regions with CNN features

## Introduction

we focused on two problems:

• localizing objects with a deep network
• training a high-capacity model with only a small quantity of annotated detection data

### localizing objects with a deep network

old way:

• approach frames localization as a regression problem may not fare well in practice
• our network is too deep to use a sliding-window

new method:

• recognition using regions
• generate proposal
• extracts a fixed-length feature vector from each proposal using a CNN
• classifies each region with category-specific linear SVMs

### scarce labeled data

old way:

• use unsupervised pre-training, followed by supervised fine-tuning

new method:

• supervised pre-training on a large auxiliary dataset
• followed by domain-specific fine-tuning on a small dataset

## Object Detection with R-CNN

three modules:

• generates category-independent region proposals
• a large convolutional neural network that extracts a fixed-length feature vector from each region
• a set of class-specific linear SVMs

### module design

#### region proposals

use selective search to enable a controlled comparison with prior detection work

use fast mode of selective search

#### feature extraction

use AlexNet

##### transformations
• isotropically scales
• with context(B)
• without context(C)
• anisotropically scales(D)

The amount of context padding (p) is defined as a border size around the original object proposal in the transformed input coordinate frame

warping with context padding (p = 16 pixels) outperformed

### test-time detection

given all scored regions in an image, we apply a greedy non-maximum suppression

#### run-time analysis

two properties make detection efficient:

• all CNN parameters are shared across all categories
• the feature vectors computed by the CNN are low-dimensional

13s/image on a GPU or 53s/image on a CPU

scalable:

• CNN feature are class-independent
• The only class-specific computations are dot products

this analysis shows that R-CNN can scale to thousands of object classes without resorting to approximate techniques

### training

#### supervised pre-training

using image-level annotations only (bounding- box labels are not available for this data)

#### domain-specific fine-tuning

continue CNN training using only warped region proposals

the last layer is randomly initialized (N + 1)-way classification —— where N is the number of object classes, plus 1 for background

We treat all region proposals with ≥ 0.5 IoU overlap with a ground-truth box as positives for that box’s class and the rest as negatives

learning rate 0.001

In each SGD iteration, we uniformly sample 32 positive windows (over all classes) and 96 background windows to construct a mini-batch of size 128

#### object category classifier

Question:

• how to label a region that partially overlaps ground-truth?

• We resolve this issue with an IoU overlap threshold
• negatives: proposal regions which IoU below threshold are defined as negatives
• positives: defined simply to be the ground-truth bounding boxes for each class
• threshold is 0.3 selected by a grid search
• proposals that fall into the grey zone (more than 0.3 IoU overlap, but are not ground truth) are ignored
##### Positive vs. negative examples and softmax

Question:

• Why are positive and negative examples defined differently for fine-tuning the CNN versus training the object detection SVMs?

• fine-tuning data is limited
• proposals with overlap between 0.5 and 1, expands the number of positive examples by approximately 30x

Question:

• Why, after fine-tuning, train SVMs at all?

• definition of positive examples used in fine-tuning does not emphasize precise localization

## Visualization, Ablation and Modes of Error

### visualizing learned features

We propose a simple (and complementary) non-parametric method that directly shows what the network learned

• compute the unit’s activations on a large set of held-out region proposals
• sort the proposals from highest to lowest activation
• perform non- maximum suppression

### ablation studies

Performance layer-by-layer

#### without fine-tuning

features from fc7 generalize worse than features from fc6

#### with fine-tuning

The boost from fine-tuning is much larger for fc6 and fc7 than for pool5

#### comparison to recent feature learning method

All R-CNN variants strongly outperform the three DPM baselines

### network architectures

the choice of architecture has a large effect on R-CNN detection performance

### detection error analysis

we applied the excellent detection analysis tool from Hoiem et al.23

### bounding-box regression

we train a linear regression model to predict a new detection window given the pool5 features for a selective search region proposal

The input to our training algorithm is a set of N training pairs ${(P^i, G^i)}_{i = 1,\dots ,N}$ where $P^i = (P^i_x, P^i_y, P^i_w, P^i_h)$ specifies the pixel coordinates of the center of proposal $p^i$’s bounding box together with $P^i$’s width and height in pixels

ground-truth bounding box G is specified in the same way

our goal is to learn a transformation that maps a proposed box P to a ground-truth box G

we parameterize the transformation in terms of four functions $d_x(P), d_y(P), d_w(P), d_h(P)$

we can transform an input proposal P into a predicted ground-truth box $\hat G$ by applying the transformation:

• $\hat G_x = P_wd_x(P) + P_x$
• $\hat G_y = P_hd_y(P) + P_y$
• $\hat G_w = P_wexp(d_w(P))$
• $\hat G_h = P_hexp(d_h(P))$

we learn $w_*$ by optimizing the regularized least square objective:

where $\phi_5$ is pool5 features of proposal P and $t$ is calculated by ground-truth value

subtle issues:

• regularization is important($\lambda = 1000$)
• care must be taken when selecting which training pairs (P, G) to use(only use IoU >= 0.6)

we found that iterating does not improve results

skip

## The ILSVRC2013 Detection Dataset

less homogeneous than PASCAL VOC

### dataset overview

train (395,918), val (20,121), and test (40,152)

our general strategy is to rely heavily on the val set and use some of the train images as an auxiliary source of positive examples

### region proposals

we followed the same region proposal approach that was used for detection on PASCAL

### training data

we formed a set of images and boxes that includes all selective search and ground-truth boxes from val1 together with up to N ground-truth boxes per class from train

An initial experiment indicated that mining negatives from all of val1, versus a 5000 image subset (roughly half of it), resulted in only a 0.5 percentage point drop in mAP, while cutting SVM training time in half

The bounding-box regressors were trained on val1

### validation and evaluation

we validated data on the val2 set

### ablation study

essentially no difference between N = 500 and N = 1000

### relationship to OverFeat

OverFeat can be seen (roughly) as a special case of R-CNN

• selective search vs multi-scale pyramid
• per-class bounding-box regressors vs single bounding-box regressor

It is worth noting that OverFeat has a significant speed advantage over R-CNN(9x faster)

## Semantic Segmentation

### CNN features for segmentation

we evaluate three strategies for computing features on CPMC regions:

• (full) ignores the region’s shape and computes CNN features directly on the warped window
• (fg) computes CNN features only on a region’s foreground mask
• (full+fg) simply concatenates the full and fg features

### results on VOC 2011

• layer fc6 always outperforms fc7
• the context provided by the full features is highly informative even given the fg features

## Conclusion

two insights:

• The first is to apply high-capacity convolutional neural networks to bottom-up region proposals in order to localize and segment objects
• The second is a paradigm for training large CNNs when labeled training data is scarce.

## Reference

23. D. Hoiem, Y. Chodpathumwan, and Q. Dai. Diagnosing error in object detectors. In ECCV. 2012.


text:
Documentation

This is machine translation

Translated by
Mouseover text to see original. Click the button below to return to the English version of the page.

beta

Syntax

```B = beta(Z,W) ```

Description

`B = beta(Z,W)` computes the beta function for corresponding elements of arrays `Z` and `W`. The arrays must be real and nonnegative. They must be the same size, or either can be scalar.

Examples

In this example, which uses integer arguments,

```beta(n,3) = (n-1)!*2!/(n+2)! = 2/(n*(n+1)*(n+2))```

is the ratio of fairly small integers, and the rational format is able to recover the exact result.

```format rat beta((0:10)',3) ans = 1/0 1/3 1/12 1/30 1/60 1/105 1/168 1/252 1/360 1/495 1/660 ```

collapse all

Beta Function

The beta function is

`$B\left(z,w\right)={\int }_{0}^{1}{t}^{z-1}{\left(1-t\right)}^{w-1}dt=\frac{\Gamma \left(z\right)\Gamma \left(w\right)}{\Gamma \left(z+w\right)}$`

where Γ(z) is the gamma function.

Algorithms

`beta(z,w) = exp(gammaln(z)+gammaln(w)-gammaln(z+w))`


text:
# Feynman diagram K decay

1. May 28, 2012

### nonequilibrium

Looking at, say, the decay $K^+ \to \pi^+ + \pi^+ + \pi^- + \gamma$, is it easy to say what the Feynman diagram is of highest contribution? I suppose it is not unique, but say we're satisfied with just one of highest order. Is there as it were a sort of flowchart one follows? For example, since strangeness is not conserved, we'll at least need one weak interaction. This will increase the number of quarks from 2 to 4. We need 2 more, for this we can use any of the interactions, hence we use the strong interaction, as it has the highest contribution. To get an outgoing photon, it seems best to simply attach a photon line to an arbitrary fermion line already present. This gives me the following drawing

Firstly, is this drawing indeed one of the highest order contributions? Secondly, is the reasoning solid? Thirdly, do you use some kind of flowchart/algorithm/step-by-step procedure to find such things? Or perhaps it's all computers? Or random guessing...

File size:
6.7 KB
Views:
334


text:
Hey! I'm David, the author of the Real-World Cryptography book. I'm a crypto engineer at O(1) Labs on the Mina cryptocurrency, previously I was the security lead for Diem (formerly Libra) at Novi (Facebook), and a security consultant for the Cryptography Services of NCC Group. This is my blog about cryptography and security and other related topics that I find interesting.

# Pairing-based polynomial commitments and Kate polynomial commitments posted June 2021

There's this thing called a Kate polynomial commitment, which is a polynomial commitment primitive that makes use of pairings. There's an excellent post from Dankrad which I would recommend reading instead of this post. I wrote this as a shorter summary of how you can commit to a polynomial, and then prove any evaluation $f(x) = y$.

Here's how it works:

You have a polynomial $f(x) = x^2 + 3x$

and some public parameters:

$$SRS = {[1], [s], [s^2], [s^3]} = {G, sG, s^2 G, s^3 G}$$

where $[x] := xG$ for some generator $G$ of an elliptic curve group.

and $s$ is a toxic waste (something that no one should know) hidden behind an elliptic curve point G (some people call that "hidden in the exponent").

## to commit to $f$

To commit to this polynomial, evaluate it at the unknown point $s$. You can do that by playing with the $SRS$:

$$[f(s)] := [s^2] + 3 [s] = s^2 G + 3 sG = (s^2 + 3s)G$$

## to prove that $f(\zeta) = a$

One day, the verifier asks "what's the evaluation at $\zeta$?" And the prover responds by sending the answer, $a$, and a proof ($h(s)$, see below).

### The idea behind the proof

Notice that because $\zeta$ is a root of $f(x)-f(\zeta)$, then for some polynomial $h(x)$:

$$f(x) - f(\zeta) = (x-\zeta) \cdot h(x)$$

Due to this, $h(x) = \frac{f(x)-f(\zeta)}{x-\zeta}$ must be a valid polynomial.

At a high-level:

• the verifier will compute what they think $[h(x)]$ should be at some random point $s$
• the prover will send the actual value $[h(s)]$
• the verifier will check if they match

This works because the Schartz-Zippel lemma tells us that two polynomials that are different are different in most points.

### The proof

Here's the protocol:

1. the prover sends the verifier a commitment $[\frac{f(s)-f(\zeta)}{s-\zeta}]=[h(s)]$ evaluated at some random point $s$ (the toxic waste).
2. the verifier constructs a similar $h(s)$ but with the expected value of $f(\zeta)$ instead: $[\frac{f(s) - a}{s-\zeta}]$. The prover then checks if it's equal to $[h(s)]$.

Note:

1. The prover can compute $[h(s)]$ easily, because they can just compute the polynomial $h(x)$ first, and then reconstruct it at $s$ with the $SRS$. $$h(x) = \frac{f(x)-f(\zeta)}{x-\zeta} = a_0 + a_1x + a_2x^2 + \cdots$$ and then $$[h(s)] := a_0[1] + a_1[s] + a_2[s^2] + \cdots$$

for example with our previous $f(x)$ and $\zeta = 3$

2. The verifier cannot compute their own $[h(s)]$ because they cannot divide by $s$ (remember, nobody knows $s$). They need a pairing. Remember, you want to check the following identity hidden in the exponent (using commitments): $$\frac{[f(s) - a]}{[s-\zeta]} = [h(s)]$$ But since you can't divide with commitments, you can't compute what's on the left-hand side. You can multiply thanks to pairings though. So instead, you could check the following equation: $$[f(s) - a] = [(s-\zeta)h(s)]$$ and with pairings, you can multiply $[s-\zeta]$ with the proof $[h(s)]$: $$e([f(s)] - [a], [1]) = e([s-\zeta], [h(s)])$$
comment on this story

# I'm now at O(1) Labs working on Mina protocol!!! posted May 2021

Hey reader! I haven't posted in a while, but as this is my blog I'm contracted to talk about life events such as this one. I've joined O(1) Labs a bit more than a month ago to work on the Mina cryptocurrency. If you don't know about Mina, check it out, it's pretty cool: it uses recursive zero-knowledge proofs to compress a blockchain into a single proof of 11KB. I hope I got you intrigued! I want to say it is one of, if not the most, ambitious project in the space (but I'm biased). As I'm still relatively new there, I don't have much to say besides that, but you can imagine that my posting will switch to more zero-knowledgy type of stuff very soon!

comment on this story

# WTF are these security chips? posted April 2021

There seem to be a few interesting trends in “security via hardware” these days.

The first trend is root-of-trust chips. Integrated TPM-like chips that are like crypto Swiss Army knives as they offer many functionalities out of the box. They resemble discrete TPMs but are instead implemented as coprocessor to the main processor. This makes these newer chips more resistant to physical MITM attacks (as discrete TPMs simply use a bus to communicate with other components). If you don’t know what a TPM is, it’s just a device that performs cryptographic operations and generally sits somewhere on your motherboard. Examples of these integrated security chips are Microsoft’s Pluton and Apple’s secure enclave.

The second trend is confidential computing. There are two types of specialized hardware here:

• Programmable integrated secure processors; these are similar to the root-of-trust chips, except that they are programmable: you can push code there and run it in a separate trusted execution environment (TEE). It’s pretty useful for applications that require a trusted computing base (TCB); a core program whose security is critical and that does not need to trust the rest of the system. It’s also useful in “cloud scenarios” where you want to run some computation on a remote machine but want to make sure it runs it correctly. Think about Intel SGX, or ARM TrustZone.
• Confidential VMs; imagine a hardware hypervisor that can run VMs as enclaves. This is usually much more practical than the enclave created by SGX, as you don’t need to write custom code and there are no memory limitation. But it is not clear to me how much security you lose against physical attacks by doing this (especially when papers like this one seem alarming). AMD SEV does this, and both Azure and GCP have started offerings to leverage this technology.

It can be hard to understand the difference between all these types of specialized hardware, the attacks they prevent, and the features they unlock. But essentially, here’s how I think about the two kinds: they all do great against software attacks (minus complex cryptographic attacks), they both aren’t the best tool in the box against a motivated physical attacker (HSMs are “better”), and only confidential computing cares about custom user code.

But it’s easier to understand the difference by looking at some examples. As I only touch on protocols, you can simply imagine these chips as creating a blackbox for code and data that others can’t see and touch (even with a debugger).

## Protecting keys and data with a secure enclave

The simplest use case for hardware security chips is to protect data. To protect keys, it’s easy: just generate them in the secure chip and disallow extraction. If you need ‘em, just ask the secure enclave to perform crypto operations with them. To protect data? Encrypt it! That concept is called file-based encryption (FBE) if you’re encrypting individual files, and full-disk encryption (FDE) if it’s the whole disk. FDE sounds much better, as it’s all or nothing. If you're under the shower and you wet your hair a little, you know you'll have to wash them. That’s what most laptops and desktops use.

In practice, FDE is not that great though: it doesn't take into account how we, human beings, use our devices. We often leave them locked, as opposed to turned off, so that background functionalities can keep running. Computers deal with this by just keeping the data-encryption key (DEK) around, even if your computer is locked. Think about that the next time you go to the restroom at Starbucks, leaving your locked computer unattended. Phones do it a bit better by encrypting different types of files depending on if your phone is locked or turned off. It sounds like a good solution, but Zinkus et al. showed that it’s not that great either.

If done well, this is how you typically hear about disk encryption in the news:

A couple of months ago the highly-publicised case of Apple vs. FBI brought attention to the topic of privacy - especially in the context of mobile devices. Following the 2015 San Bernardino terrorist attack, the FBI seized a mobile phone belonging to the shooter, Syed Farook, with the intent to search it for any additional evidence or leads related to the ongoing investigation. However, despite being in possession of the device, the FBI were unable to unlock the phone and access its contents.

Of course, the user should be authenticated before data can be decrypted. This is often done by asking the user for a PIN or password. A PIN or password is not enough though, as it would allow simple brute-force attacks (especially on 4 or 6-digit PINs). In general, solutions try to tie the DEK to both a user credential and a symmetric key kept on the enclave.

What’s that symmetric key? We all know that you can’t hardcode the same key in every device you produce. This is dumb. You end up with attacks like DUHK where thousands of devices are found hardcoding the same secret (and pwning one device breaks all of them). The solution is a per-device key that is either burned into the chip during manufacturing, or created by the chip itself (so-called physically unclonable functions). For example, each Apple secure enclave have a UID, each TPM has a unique endorsement key and attestation key, each OpenTitan chip has a creator root key and an owner root key, etc.

A randomly generated UID is fused into the SoC at manufacturing time. Starting with A9 SoCs, the UID is generated by the Secure Enclave TRNG during manufacturing and written to the fuses using a software process that runs entirely in the Secure Enclave. This process protects the UID from being visible outside the device during manufacturing and therefore isn’t available for access or storage by Apple or any of its suppliers. sepOS uses the UID to protect device-specific secrets. The UID allows data to be cryptographically tied to a particular device. For example, the key hierarchy protecting the file system includes the UID, so if the internal SSD storage is physically moved from one device to another, the files are inaccessible.

To prevent brute-force attacks, Apple’s secure enclave mixes both the UID key and the user PIN with a password-based KDF (password-hashing function) to derive the DEK. Except that I lied: to allow user to change their PIN quickly, the DEK is actually not derived directly, but instead encrypted by a key-encryption key (KEK).

## Secure boot with a root-of-trust secure chip

When booting your computer, there are different “stages” that will run until you finally get to the screen you want. One problem users face are viruses and malwares, and these can infect the boot process. You then run on an evil operating system… To protect the integrity of boot, our integrated secure chips provide a “root of trust”, something that we trust 100% and that allows us to trust other stuff down the line. This root of trust is generally some read-only memory (ROM) that cannot be overwritten, and it’s also called one-time programmable memory as it was written during manufacturing and can’t be changed anymore. For example, when powering up a recent Apple device, the very first code that gets executed is inside the Apple’s secure enclave ROM (called Boot ROM). That boot rom is tiny, so usually the only thing it does is:

• Prepare some protected memory and loads the next image there (so-called "boot code").
• Hash the image and verify its signature against the hardcoded public key in the ROM.
• Execute that code.

The next boot loader does the same thing, and so on until it gets to the device’s operating system. This is how updates that are not signed by Apple can’t be installed on your phone.

## Confidential Computing with a programmable secure processor

There’s been a new paradigm for the last years: the cloud; big companies running servers to host your stuff. Amazon has AWS, Google has GCP, and Microsoft has Azure. Another way to put this is that people are moving from running things themselves, to running things on someone else’s computer. This of course create some issues in some scenarios where privacy is important. To fix that, confidential computing attempts at offering solutions to run client code without being able to see it or modify its behavior. SGX primary use case seems to be exactly that these days: clients running code that the servers can’t see or tamper with.

One interesting problem that arise is: how can I trust that the response I got from my request indeed came from SGX, and not some impersonator. This is what attestation tries to solve. There are two kinds of attestation:

• local attestation, when two enclaves running on the same platform need to communicate and prove to each other that they are secure enclaves
• remote attestation, when a client queries a remote enclave and need to make sure that it was a legit enclave that produced the result from the request.

Each SGX chip is provided with unique keypairs at manufacturing time: the Root Sealing Keys. The public key part is then signed by some Intel certificate authority. So the first assumption, if we ignore the assumption that the hardware is secure, is that Intel is correctly signing public keys of secure SGX chips only.

With that in mind, you can now obtained a signed attestation, from Intel's CA, that you're talking to a real SGX enclave, and that it is running some code (at least a proof of its digest), etc.

comment on this story

# What is Host Card Emulation (HCE)? posted April 2021

It’s 2020, most people have a computer in their pocket: a smart phone. What is the point of a credit card anymore? Well, not much. Nowadays more and more payment terminals support contactless payment via the near-field communication (NFC) protocol, and more and more smartphones ship with an NFC chip that can act as a credit card. NFC for payment is specified as Card Emulation. Literally: it emulates a bank card. But not so fast, banks will prevent you from doing this unless you have a secure element.

Since Apple has full control over its hardware, it can easily add a secure element to its new iPhones to support payment, and this is what Apple did with an embedded secure element bonded onto the NFC chip since the iPhone 6. The secure element communicates directly with the NFC chip, and in turn to NFC readers; thus a compromise of the phone operating system does not impact the secure element.

Tokenization is a common concept in security: replace the sensitive data with some random stuff, and have a table secured somewhere safe that maps the random stuff to the real data. Although Apple theoretically doesn't have to use tokenization, since iPhones have secure elements that can store the real Primary Account Number (PAN), they do use it in order to gain more privacy (it's after all their new bread and butter).

comment on this story

# One password to rule them all, single sign-on (SSO) and password managers posted April 2021

Password reuse is bad, what can we do about it? Naively, users could use different passwords for different websites, but there are two problems with this approach:

To alleviate these concerns, two solutions have been widely adopted:

• Single-sign on (SSO). The idea of SSO is to allow users to connect to many different services by proving that they own the account of a single service. This way the user only has to remember the password associated with that one service in order to be able to connect to many services. Think "connect with Facebook" type of buttons, as illustrated below.
• Password Managers. The previous SSO approach is convenient if the different services you use all support it, but this is obviously not scalable for scenarios like the web. A better approach in these extreme cases is to improve the clients as opposed to attempting to fix the issue on the server side. Nowadays, modern browsers have built-in password managers that can suggest complex passwords when you register on new websites, and can remember all of these passwords as long as you remember one master password.

An example of single-sign on (SSO) on the web. By having an account on Facebook or Google, a user can connect to new services (in this example Airbnb) without having to think about a new password.

The concept of SSO is not new in the enterprise world, but its success with normal end-users is relatively recent. Today, two protocols are the main competitors when it comes to setting up SSO:

• Security Assertion Markup Language 2.0 (SAML). A protocol using the Extensible Markup Language (XML) encoding.
• OpenID Connect (OIDC). An extension to the OAuth 2.0 (RFC 6749) authorization protocol using the JavaScript Object Notation (JSON) encoding.

SAML is still widely used, mostly in an enterprise setting, but it is at this point a legacy protocol. OpenID Connect, on the other hand, can be seen everywhere on web and mobile applications. You most likely already used it!

While OpenID Connect allows for different types of flows, let's see the most common use case for user authentication on the web via the authorization code flow:

1. Alice wants to log into some application, let's say example.com, via an account she owns on cryptologie.net (that's just my blog, but let's pretend that you can register an account on it).
2. example.com redirects her browser to a specific page of cryptologie.net to request an "authorization code." If she is not logged-in in cryptologie.net, the website will first ask her to log in. If she is already logged-in, the website will still confirm with the user that they want to connect to example.com using their identity on cryptologie.net (it is important to confirm user intent).
3. cryptologie.net redirects Alice back to example.com which then learns the authorization code.
4. example.com can then query cryptologie.net with this authorization code to confirm Alice's claim that she owns an account on cryptologie.net, and potentially retrieve some additional profile information about that user.

In OpenID Connect (OIDC), Alice (the end-user in OIDC terms) can authenticate to a service example.com (the relying party) using her already existing account on cryptologie.net (the OpenID provider). For the web, the authorization code flow of OIDC is usually used. It starts by having Alice request an "authorization code" from cryptologie.net (and that can only be used by example.com). example.com can then use it to query cryptologie.net for Alice's profile information (encoded as an ID token), and then associate her cryptologie.net identity with an account on their own platform.

There are many important details that I am omitting here. For example, the authorization token that Alice receives in step 2 must be kept secret, as it can be used to log in as her on example.com. Another example: so that example.com cannot reuse the authorization token to connect as Alice on a different website, the OpenID provider cryptologie.net retains an association between this authorization token and the intended audience (example.com). This can be done by simply storing this association in a database, or by having the authorization code contain this information authenticated (I explained a similar technique with cookies in chapter 3).

By the way, the proof given to example.com in step 4 is called an ID token in OpenID Connect, and is represented as a JSON Web Token (JWT) which is just a list of JSON-encoded data.

In OpenID Connect, if Alice wants to log in on example.com via her account on another website (an OpenID provider), example.com eventually needs to obtain what is called an "ID token." An ID token is some user information encoded via the JSON Web Token (JWT) standard. a JWT is simply the concatenation of three JSON-encoded objects. In the picture, the website https://jwt.io lets you decode a JWT and learn what every field stands for. In our browser-based example, example.com uses TLS to communicate with (and authenticate) the OpenID provider. Thus, the ID token it receives can be trusted. In other OpenID Connect flows (used, for example, by mobile applications) the ID token can be provided directly by the user, and can thus be tampered with. In this case, an ID token contains a signature which can be verified using the OpenID provider's public key.

Authentication protocols are often considered hard to get right. OAuth2, the protocol OpenID Connect relies on, is notorious for being easy to mis-use (see RFC 6819: OAuth 2.0 Threat Model and Security Considerations). On the other hand, OpenID Connect is very well specified. Make sure that you follow the standards and that you look at best practices, this can save you from a lot of trouble.

Here's another example of a pretty large company deciding not to follow this advice. In May 2020, the "Sign-in with Apple" SSO flow that took a departure from OpenID Connect was found to be vulnerable. Anyone could have obtained a valid ID token for any Apple account, just by querying Apple's servers.

SSO is great for users, as it reduces the number of passwords they have to manage, but it does not remove passwords altogether. The user still has to use passwords to connect to OpenID providers. If you're interested to know how cryptography can help to hide passwords, read the rest of this content in my book real-world cryptography.

comment on this story

# Cryptography and assembly code posted March 2021

Thanks to filippo streaming his adventures rewriting Golang assembly code into "cleaner" Golang assembly code, I discovered the Avo assembly generator for Golang.

This post is not necessarily about Golang, but Golang is a good example as its standard library is probably the best cryptographic standard library of any programming language.

At dotGo 2019, Michael McLoughlin presented on his Avo tool. In the talk he mentions that there's 24,962 x86 assembly lines in Golang's standard library, and most of it is in the crypto package. A very "awkward" place where "we need very high performance, and absolute correctness". He then shows several example that he describes as "write-once code".

The talk is really interesting and I recommend you to check it.

I personally spent days trying to understand Golang's SHA-3 assembly implementation. I even created a Go Assembly by Example page to help me in this journey. And I ended up giving up. I just couldn't understand how it worked, the thing didn't make sense. Someone had written it with their own mental model of how they wanted to pass data around. It was horrible.

It's not just a problem of Golang. Look at OpenSSL, for example, which most cryptographic applications and libraries rely on. It contains a huge amount of assembly code to implement cryptography, and that assembly code is sometimes generated by unintelligible perl code.

There are many more good examples out there. the BearSSL TLS implementation by Thomas Pornin, the libsodium cryptographic library by Frank Denis, the extended keccak code package by the Keccak team, all use assembly code to produce fast cryptography.

We're making such a fuss about readable, auditable, simple and clear cryptographic implementations, but most of that has been thrown out of the window in the quest for performance.

The real problem, from a reviewer perspective is that assembly is getting us much further away from the specification. As the role of a reviewer is to match the implementation to the specification, it makes the job hard, perhaps impossible.

Food for thoughts...

1 comment

# Key wrapping and nonce-misuse resistance posted March 2021

If you know about authenticated encryption, you could stop reading here, understand that you can just use AES-GCM or Chacha20-Poly1305 whenever you need to encrypt something, and move on with your life. Unfortunately real-world cryptography is not always about the agreed standard, it is also about constraints. Constraints in size, constraints in speed, constraints in format, and so on. For this reason, we need to look at scenarios where these AEADs won't fit, and what solutions have been invented by the field of cryptography.

## Wrapping keys: how to encrypt secrets

One of the problem of nonce-based AEADs is that they all require a nonce, which takes additional space. In worse scenarios, the nonce to-be-used for encryption comes from an untrusted source and can thus lead to nonce repetition that would damage the security of the encryption. From these assumptions, it was noticed that encrypting a key might not necessarily need randomization, since what is encrypted is already random.

Encrypting keys is a useful paradigm in cryptography, and is used in a number of protocol as you will see in the second part of this book.

The most widely adopted standard is NIST Special Publication 800-38F, Recommendation for Block Cipher Modes of Operation: Methods for Key Wrapping. It specifies two key wrapping algorithms based on AES: the AES Key Wrap (KW) mode and the AES Key Wrap With Padding (KWP) mode.

These two algorithms are often implemented in Hardware Security Modules (HSM). HSMs are devices that are capable of performing cryptographic operations while ensuring that keys they store cannot be extracted by physical attacks. That's at least if you're under a certain budget.

These key-wrapping algorithms do not take an additional nonce or IV, and randomize their encryption based on what they are encrypting. Consequently, they do not have to store an additional nonce or IV next to the ciphertexts.

## AES-GCM-SIV and nonce-misuse resistance authenticated encryption

In 2006, Rogaway published a new key-wrapping algorithm called Synthetic initialization vector (SIV), as part of Deterministic Authenticated-Encryption: A Provable-Security Treatment of the Key-Wrap Problem. In the white paper, Rogaway notes that the algorithm is not only useful to encrypt keys, but as a general AEAD algorithm as well that is resistant to nonce repetitions. As you probably know, a repeating nonce in AES-GCM or Chacha20-Poly1305 has catastrophic consequences. It not only reveals the XOR of the two plaintexts, but it also allows an attacker to recover an authentication key and to forge more messages. In Nonce-Disrespecting Adversaries: Practical Forgery Attacks on GCM in TLS, a group of researchers found 184 HTTPS servers being guilty of reusing nonces. (I even wrote here about their super-cool live demo.)

The point of a nonce-misuse resistant algorithm is that encrypting two plaintexts with the same nonce will only reveal if the two plaintexts are equal or not.

It is sometimes hard to obtain good randomness on constrained devices or mistakes can be made. In this case, nonce-misuse resistant algorithms solve real problems.

In the rest of this section, I describe the scheme standardized by Google in RFC 8452, AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption.

The idea of AES-GCM-SIV is to generate the encryption and authentication keys separately via a main key every time a message has to be encrypted (or decrypted). This is done by producing a keystream long enough with AES-CTR, the main key and a nonce:

The main key of AES-GCM-SIV is used solely with AES-CTR to derive the encryption key K and the authentication key H.

Notice that if the same nonce is used to encrypt two different messages, the same keys will be derived here.

Next, AES-GCM-SIV authenticates the plaintext, instead of the ciphertexts as we have seen in the previous schemes. This creates an authentication tag over the associated data and the plaintext (and their respective lengths). Instead of GMAC, AES-GCM-SIV defines a new MAC called Polyval. It is quite similar and only attempts to optimize some of GMAC's operations.

The Polyval function is used to hash the plaintext and the associated data. It is then encrypted with the encryption key K to produce an authentication tag.

Importantly, notice that if the same nonce is reused, two different messages will of course produce two different tags. This is important because in AES-GCM-SIV, the tag is then used as a nonce to AES-CTR in order to encrypt the plaintext.

AES-GCM-SIV uses the authentication tag (created with Polyval over the plaintext and the associated data) as a nonce for AES-CTR to encrypt the plaintext.

This is the trick behind SIV: the nonce used to encrypt in the AEAD is generated from the plaintext itself, which makes it highly unlikely that two different plaintexts will end up being encrypted under the same nonce. To decrypt, the same process is done in reverse:

AES-GCM-SIV decrypts a ciphertext by using the authentication as a nonce for AES-CTR. The plaintext recovered is then used along with the associated data to validate the authentication tag. Both tags need to be compared (in constant-time) before releasing the plaintext to the application.

As the authentication tag is computed over the plaintext, the ciphertext must first be decrypted (using the tag as an effective nonce). Then, the plaintext must be validated against the authentication tag. Because of that, one must realize two things:

• The plaintext is released by the algorithm before it can be authenticated. For this reason it is extremely important that nothing is done with the plaintext, until it is actually deemed valid by the authentication tag verification.
• Since the algorithm works by decrypting the ciphertext (respectively encrypting the plaintext) as well as authenticating the plaintext, we say that it is two-pass -- it must go over the data twice. Because of this, it usually is slower than its counterpart AES-GCM.

SIV is a powerful concept that can be implemented for other algorithms as well.

comment on this story

# Signature forgeries in Golang ECDSA library? posted March 2021

Take a look at the following program that you can run in Golang's playground.

// sign a message
r, s, err := ecdsa.Sign(rand.Reader, privateKey, hash[:])
if err != nil {
panic(err)
}

// print the signature
signature := r.Bytes()
signature = append(signature, s.Bytes()...)
fmt.Println("signature:", hex.EncodeToString(signature))

// verify the signature
if !ecdsa.Verify(&privateKey.PublicKey, hash[:], r, s) {
panic("wrong signature")
} else {
fmt.Println("signature valid for", hex.EncodeToString(hash[:]))
}

// I modify the message, this should invalidate the signature
var hash2 [32]byte
hash2[31] = 1
if !ecdsa.Verify(&privateKey.PublicKey, hash2[:], r, s) {
panic("wrong signature")
} else {
fmt.Println("signature valid for", hex.EncodeToString(hash2[:]))
}

this should print out:

signature: 4f3e60dc53ab470d23e82567909f01557f01d521a0b2ae96a111d107741d8ebb885332d790f0691bdc900661bf40c595a07750fa21946ed6b88c61c43fbfc1f3
signature valid for 0000000000000000000000000000000000000000000000000000000000000001


text:
# The interaction of pollution, meteorology and bioaerosols: implications on human health

Mahmood, Marliyyah Abdullahi (2018). The interaction of pollution, meteorology and bioaerosols: implications on human health. University of Birmingham. Ph.D.

 Preview
Mahmood18PhD.pdf
PDF - Accepted Version

## Abstract

The global incidence of allergic reaction has been rising for years, especially within westernised urban areas. There is evidence that the interaction between pollen grains, environmental pollution and meteorological change is increasing the allergenicity of the pollen grain and consequently, increasing the misery of hay fever sufferers. Laboratory experiments have shown that the interaction of pollen with atmospheric oxidants such as ozone and nitrogen dioxide ($$NO_2$$) can alter protein molecules that are present within the pollen grains via post-translational modification of the protein.

Within the laboratory, birch pollen was exposed to atmospherically relevant exposures of gas phase $$NO_2$$ and ozone under a range of environmentally relevant conditions (temperature and relative humidity RH). The effects of the exposures on the biochemistry of the pollen grains were probed using proteomic approach. The morphological changes of unexposed and exposed pollen samples to RH, rainwater and $$NO_2$$, where observed under fluorescence microscopy and scanning electron microscope. The discoveries suggest that interaction between gas pollutants and pollen do exist and cause protein specific modifications; nitration.

Detailed analysis of London Ambulance data compared to London temperature data is presented. The relationships established will allow for prediction of likely changes in ambulance demand (and illness types) that will be caused by seasonal temperature changes, increased frequency and intensity of extreme weather events, due to climate change, in the future.

The study applied statistical analyses to examine short-term associations between birch pollen count with allergic related illnesses recorded in the London Ambulance data, temperature and $$NO_2$$.

Type of Work: Thesis (Doctorates > Ph.D.)
Award Type: Doctorates > Ph.D.
Supervisor(s):
Supervisor(s)EmailORCID
Pope, FrancisUNSPECIFIEDUNSPECIFIED
Bloss, WilliamUNSPECIFIEDUNSPECIFIED
Licence:
College/Faculty: Colleges (2008 onwards) > College of Life & Environmental Sciences
School or Department: School of Geography, Earth and Environmental Sciences
Funders: Other
Other Funders: Nigerian Nuclear Regulatory Authority, Petroleum Technology Development Fund, Nigeria
Subjects: G Geography. Anthropology. Recreation > GE Environmental Sciences
Q Science > QR Microbiology > QR180 Immunology
R Medicine > RA Public aspects of medicine
URI: http://etheses.bham.ac.uk/id/eprint/8101

### Actions

 Request a Correction View Item


text:
# SHELL= (CONFIG.SYS Command)

```                                                         Compatibility: 2.0+
Purpose: Replaces the normal command processor (COMMAND.COM) with a
different program, OR selects non-default settings for
COMMAND.COM.  Note: This command is unrelated to the Dosshell
command.

Uses: ■ Identify the location of COMMAND.COM.
■ Create a DOS environment that is larger than the default.
■ Run a batch file other than AUTOEXEC.BAT at startup.

Syntax: SHELL=[d:][path]filename.ext [parms]

█▌Parameters▐█

d:\path\filename.ext is the drive, path, filename and extension of the
program to be used as the command processor.

progParms specifies command-line parameters for the command processor.

█▌TECH Notes▐█

■ The DOS 6.0 COMMAND.COM option /K= sets the name of the AUTOEXEC.BAT
file.  COMMAND.COM /K=mybat.bat is a handy way to set up a DOS session
from Windows.

■ To increase the size of the DOS environment, use COMMAND.COM /E=nnn.


text:
# The joint distribution of zeros of brownian motion

Let $\gamma_t$ be the last zero of brownian motion before $t$ and $\beta_t$ be the first zero after $t$. I need to calculate the joint distribution of $\gamma_t$ and $\beta_t$, i.e. $P(\gamma_t<x, \beta_t<y)$. I know about arcsine low for these zeroes:

$P(\gamma_t<x)=\frac{2}{\pi}\arcsin\sqrt\frac{x}{t}$

$P(\beta_t<y)=\frac{2}{\pi}\arcsin\sqrt\frac{t}{y}$

But how can I get the joint distribution?

Thanks!

-
Got something from my answer below? – Did Jul 25 '12 at 16:52

Let me assume for a moment that one knows the distribution of the first hitting time $\tau$ of level $1$ by a Brownian motion starting from $0$. By scaling and translation invariance, the first hitting time of $0$ for a Brownian motion starting from $x$ is distributed like $x^2\tau$.

For every $0\lt u\lt t\lt v$, $[\gamma_t\lt u,v\lt\beta_t]=[\gamma_v\lt u]$. The scale invariance of Brownian motion implies that $[\gamma_v\lt u]$ has the same probability as $[\gamma_1\lt u/v]$. The last event depends on $\gamma_1$ only, and one knows that the distribution of $\gamma_1$ is the Arcsine distribution. Let us briefly show this.

Conditionally on $B_{s}=x$, the event $[\gamma_1\lt s]$ corresponds to the fact that a Brownian motion starting from $x$ hits $0$ after time $1-s$, hence $$\mathrm P(\gamma_1\lt s\mid B_{s}=x)=\mathrm P(x^2\tau\gt 1-s).$$ Introducing $h(s)=\mathrm P(\tau\gt s)$ for every $s\gt0$ and writing $(g_s)_{s\gt0}$ for the transition semi-group of Brownian motion $g_s(x)=\mathrm e^{-x^2/(2s)}/\sqrt{2\pi s}$, this means that $$\mathrm P(\gamma_1\lt s)=\int_{-\infty}^{+\infty}h\left(\frac{1-s}{x^2}\right)g_s(x)\mathrm dx,$$ from which the distribution of $\gamma_1$, thus also the joint distribution of $(\gamma_t,\beta_t)$, follow by differentiation.

To complete this, recall that Désiré André's reflexion principle shows that the probability of $[\tau\lt s]$ is twice the probability of $[B_s\gt1]$, hence $$h(s)=1-2\mathrm P(B_s\gt 1)=2\int_0^1g_s(x)\mathrm dx.$$ After some simplifications and change of variables in the double integral, this leads to $$\mathrm P(\gamma_1\lt s)=\frac2\pi\arctan\left(\sqrt{\frac{s}{1-s}}\right)=\frac2\pi\arcsin\left(\sqrt{s}\right),$$ hence $$\mathrm P(\gamma_t\lt u,v\lt\beta_t)=\frac2\pi\arcsin\left(\sqrt{\frac{u}{v}}\right),$$ a formula which is all over the place, and probably in Rick Durrett's Probability Theory with Applications.

-
Thanks! But we calculate the probability $P(\gamma_t<u,\beta_t>v)$. Can we get it in the form $P(\gamma_t<u,\beta_t<v)$? – Leo May 27 '12 at 14:20
$[\gamma_t\lt u,\beta_t\lt v]=[\gamma_t\lt u,t\lt\beta_t]\setminus[\gamma_t\lt u,v\lt\beta_t]$. – Did May 27 '12 at 15:28
So in this case formula looks like:$\frac{2}{\pi}\arcsin\sqrt\frac{u}{t}-\frac{2}{\pi}\arcsin\sqrt\frac{u}{v}$ and depends on $t$? – Leo May 27 '12 at 15:39
The event $[\gamma_t\lt u,\beta_t\lt v]$ corresponds to no zero in $(u,t)$ and at least one zero in $(t,v)$ hence indeed its probability depends on $t$ (and on $u$ and $v$). – Did May 27 '12 at 16:07


text:
Cancellation of my ticket

I have booked two tickets on the same account for sleeper but I want to cancel one ticket two of them so if I cancel one ticket another is available or not

Very Recent i had created google clould platform account and gave my card details and without any idea on the top i had upgraded my free trail. i havent spent a single rupee and used any of those services so i went through google to know how to cancel my account.so finally i closed my billing account and i shut down the project my doubt is do i get billed after 90 days and what should i do to not get billed i closed the billing accoun and i shut down the project what else should i do to not get billed

air travel – What’s the point of flight ticket cancellation charges?

Many airlines sell tickets with fair rules that include a “cancellation penalty” if the ticket were to be cancelled prior to departure. Usually, this mostly applies to the economy class fare option (example), and the cancellation penalty may be waived if the ticket is cancelled within, say, 24 hours of purchase (example).

According to this Travel SE answer, most people would prefer a no-show over cancelling their ticket if that entails paying a fee. The answer also mentions that the fee exists due to “convoluted revenue optimizations systems”.

I believe that this cancellation fee functions as kind of a “service fee” in order to pay for processing the cancellation request. However, from my layman’s perspective, the fee does not make any sense. I think an airline should provide its customers with an incentive to cancel their tickets as soon as they decide they are not going to travel, instead of choosing to simply not show up. This would enable the airline to resell the seat and potentially save up on other costs such as by preparing less meals. Moreover, this will decrease the number of no-shows in general, which could reduce the need for overbooking.

So, what is the point of such fees? If it is indeed due to “convoluted revenue optimizations systems”, can somebody please elaborate on that?

covid 19 – Options under EC261 in event of partial cancellation on a multicity itinerary

I have a multi city booking on a single PNR, as follows:

• Segment 1 / Leg 1 BRS – AMS, Saturday (operated by KLM)
• Segment 2 / Leg 2 AMS – TLL, Tuesday (operated by Air Baltic)
• Segment 3 TLL-BRS Friday: comprised of leg 3 TLL – AMS (operated by Air Baltic) connecting to leg 4 AMS – BRS (operated by KLM).

Booking was with KLM, Air Baltic is a codeshare partner so those flights also carry a KL flight number.

Estonia only permits flights from airports in countries where the recent COVID morbidity is less than 25 cases per 100,000, reviewed each Friday. Unfortunately the most recent figures for the Netherlands have exceeded that since I booked. Presumably as a result, Air Baltic has been cancelling their AMS-TLL flights on a rolling basis since Friday (it looks like they wait until one or two days before departure to pull each flight, however, rather than removing a week’s worth immediately).

There are still a few weeks for the numbers to improve sufficiently that my itinerary will remain valid, but I am unsure how to parse the usual EC261 options of reimbursement, re-routing or return if there is no such improvement and hence a partial cancellation does occur. Specifically:

• If the Air Baltic flights are cancelled, am I entitled to adjust my AMS-BRS leg to some other date (ideally the Tuesday originally intended for AMS-TLL), since I would still wish to visit the Netherlands Sat-Mon?
• If I am instead expected to stick to the original AMS-BRS leg on the Friday, is there any duty of care for accommodation in the Netherlands Tuesday through Friday? Whilst my bookings in Tallinn are refundable, last minute Dutch hotels are more expensive than pre-booked Estonian ones.
• How would reimbursement be calculated if only the middle two legs are cancelled?
• Do the answers to any of the above depend on whether I have commenced travel (i.e. on whether Air Baltic cancels the flight immediately after figures are released on Friday afternoon, versus some time after I’ve arrived in the Netherlands on Saturday morning)?

Note that I am only interested in my options regarding reimbursement/return; this is not a question about seeking additional compensation. I am also aware of the awkward possibility of a COVID figure between 15 and 25, whereby the flights are allowed to operate but I would have to quarantine in Estonia for two weeks (in which case it then becomes me who would wish to cancel some legs, not Air Baltic).

nigerian citizens – Cancellation of visit visa at the airport

Stack Exchange Network

Stack Exchange network consists of 177 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Flight Cancellation information for an Avianca flight [duplicate]

I need to find information regarding an Avianca Flight from Baltra Island (Galapagos Islands) to Quito. We had a stop in the Guayaquil Airport. We were not to depart the plane but then they cancelled our flight to Quito with no help to change our flights as the Quito Airport was not accepting flights due to the unrest in the country.

compensation – How do I check the true cause of a flight cancellation?

(DUS=Düsseldorf, FRA=Frankfurt, MAN=Manchester, NCL=Newcastle, PRN=Prishtina, VIE=Vienna)

Originally had a Eurowings booking PRN-DUS-NCL and a rail ticket Newcastle-Manchester, whereby I would’ve landed at NCL at 10:40, then reached Manchester at 14:20.

15 days before departure, the DUS-NCL flight was cancelled and I was re-booked to PRN-DUS-MAN, whereby I would’ve landed at MAN at 14:40.

3 days before departure, the PRN-DUS flight was cancelled.

1 day before departure, I was re-booked to PRN-VIE-FRA-MAN with Austrian+Lufthansa (I understood Eurowings wouldn’t do this willingly, but made it clear straight away that I would drag them to court if they tried conning me, and they got the hint). Ended up with this and landed at MAN at 22:55.

A week ago I e-mailed claims261@eurowings.com asking for:

• EUR 400 compensation per EC261
• Reimbursement for the unusable, nonrefundable rail ticket Newcastle-Manchester (GBP 10.55).

I told them that, should extraordinary circumstances per EC261 apply, they are to provide a detailed explanation with relevant documentation. I added that I may check the accuracy of their information with the relevant authorities, “adivising against” giving incorrect/misleading information.

(airlines will happily claim “since there happens to be an ongoing pandemic, everything counts as an extraordinary circumstance, so you can’t claim for anything ever”. This is emphatically NOT true.)

FWIW, the PRN-DUS route wasn’t cancelled altogether, just reduced. I made screenshots proving it took off two days before and one day after my date.

I got a “read” receipt very quickly, but no response yet.

NOW, my question is: what German authority can check whether an airline is being truthful about the reason for a cancellation? The EU’s list of national enforcement bodies refers to the Luftfahrt-Bundesamt, but someone told me they only accept cases where there’s concrete evidence of an airline violating EC261, not examining whether an airline is truthful or not.

Third-party agents such as Claimcompass do deal with such examinations, but would keep 35% for themselves, so I want to avoid going through them if at all possible.

So in summary: what authority in Germany do I turn to? Or is it perhaps the Kosovan civil aviation authority?

history of gaming – What factors led to the poor reception and early cancellation of Wraith: The Oblivion?

Wraith: The Oblivion was published by White Wolf Games in 1994, but cancelled in 1999. Many of the books during the run show signs of being compressed together. While White Wolf typically published one book for each clan, bloodline, creed, etc., for Wraith two guilds were often smashed into one book. Wikipedia says that more books were planned, but never published.

Why was Wraith cancelled early? Wikipedia also mentions it was nominated for some awards, and it seems like a fairly novel game in some regards. It has a unique character that really sets it apart. I haven’t played it, but reading the books doesn’t reveal anything telling – it seems to use the same system as other White Wolf games with some reskinning.

Things I’ve tried:

• I’ve tried asking the proprieters of my local game stores. They either don’t know anything, or remember that it sold poorly with no real explanation.
• I’ve asked around my local World of Darkness tables. Many of the oldbies were playing in the 1990’s, but none admit to having played the game. Their responses mostly came down to “everyone knows this game sucks”, with no explanation of why.
• White Wolf advertised some listservs in its game books, but I haven’t been able to find archives of them.
• I’ve read some reviews of Wraith. Most of them are rather artistic or critical in nature, rather than something that I suspect reflects the real played experience of actual tables. Additionally, none of them describe the game’s failure or why it was cancelled.

So what happened? Why was Wraith cancelled?

Cancellation of inequalities in floating point arithmetic

In finite precision floating point arithmetic the associative property of addition is not satisfied. This is, it is not always the case that $$(a+b)+c=a+(b+c)$$
Even $$a=(a+b)-b$$ is not always true.

To prove that $$x+y is equivalent to $$x with real numbers we can add $$-y$$ on both sides of $$x+y to get $$(x+y)-y and then from this $$x=x+(y-y). But I can’t repeat the last step for floating point.

Question 1: Are the inequalities $$x+y and $$x equivalent in finite precision floating point arithmetic?

Question 2: Are the inequalities $$x+yleq z$$ and $$xleq z-y$$ equivalent in finite precision floating point arithmetic?

Motivation: There is that interview problem that given an ordered array of numbers and a threshold it asks for the number of pairs of numbers of the array which sum is not larger than the threshold. Possible solutions aside, I wanted to understand the particular point of the dangers of switching between testing $$x+y (and also $$leq$$ depending on which variant of the problem is presented) and testing $$x (or $$leq$$).

Ryanair COVID-19 cancellation and following flight

Ryanair canceled due COVID-19 my flight Prague to Milan (Bergamo) which will be on 23 June 2020. But I had following flight from Milan Malpensa (T2) to Alghero (Sardinia) with Easyjet, which I’m not able to use. Can I ask Ryanair also to get refunds for my easyjet tickets?